5

鉴于：

  • String中的一些字符input。
  • 一个整数N

如何生成具有确切长度 N 的所有可能单词？

如果我有input = {"a", "b", "a"}and N=2，那么输出应该是：（ab,aa,ba没有重复）

我搜索了这个，我得到的只是一些我无法理解的算法，而不是实现。我知道我需要实现一个递归方法，但是我在停止条件之后被卡住了。

public void generate(String input, int length) {        
    if(length == 0) {
        System.out.println(input);
        return;
    }
    //Not sure about this part
    String[] a = input.split("");
    for(int i =0; i<a.length; i++) {
        loop(input+a[i], length-1);
    }
}
4

2 回答 2

1

这应该可以解决问题并与任何inputand一起使用N。行为没有很好地定义N = 0或N > input.length() 

public static void generate(String input, int N) {
    generate("", input, new HashSet<String>(), N);
}

private static void generate(String str, String input, Set<String> dup, int N) {
    if (str.length() == N && dup.add(str))
        System.out.println(str);
    else
        //remove a char form input and add it to str
        for (int i = 0; i < input.length(); i++)
            generate(
                str + input.charAt(i), 
                input.substring(0, i) + input.substring(i + 1), 
                dup, N);
}

这已改编自更一般的“计算所有排列”问题。在一般问题中没有重复检查并且str在input.isEmpty(). 如果您需要任何澄清，请告诉我。

于 2013-07-20T07:10:32.737 回答
0

这也适用于空字符串或 n == 0。

重载是第二种重载combination()方法（采用四个参数的方法）。第一个重载只是将输入字符串转换为 aList<Character>并准备一个空的哈希集来存储结果：

Set<String> combination(String input, int n) {
  List<Character> letters = new ArrayList<Character>();
  for (int i = 0; i < input.length(); ++i)
    letters.add(input.charAt(i));
  Set<String> results = new HashSet<String>();
  combination("", letters, n, results);
  return results;
}

void combination(String soFar, List<Character> letters, int n, 
    Set<String> results) {
  if (n == 0) { 
    results.add(soFar);
    return;
  }

  int startIndex = soFar.length();
  if (startIndex >= letters.size())
    return;      

  for (int i = startIndex; i < letters.size(); ++i) {
    // ch is the next candidate to add to the result that we're 
    // building (soFar)
    char ch = letters.get(i); 
    // Swap the characters at positions i and position startIndex.
    char temp = letters.get(startIndex);
    letters.set(i, temp);
    letters.set(startIndex, ch);

    // add ch to soFar, compute combinations of length n-1.
    // as startIndex is essentially soFar.length() this means that 
    // the recursive call will only process the remainder of the list.
    combination(soFar + ch, letters, n - 1, result);

    // Swap the characters back - restore the original state.
    letters.set(i, ch);
    letters.set(startIndex, temp);
  }
于 2013-07-20T13:49:52.637 回答