java - 使用递归通过迭代器查找字符串的排列

Question

正如标题所暗示的，我很难尝试递归地确定给定String的所有排列。问题是 String 必须通过对象的构造函数给出，然后一一找到每个排列。基本上，它必须像这样工作:

PermutationIterator iter = new PermutationIterator("eat");
while (iter.hasMorePermutations())
   System.out.println(iter.nextPermutation());

这是我正在使用的代码，但似乎不起作用，而且我不知道如何修复它。

public class PermutationIterator {

    private String word;
    private int pos;
    private PermutationIterator tailIterator;
    private String currentLetter;

    public PermutationIterator(String string) {
        word = string;
        pos = 0;
        currentLetter = string.charAt(pos) + "";
        if (string.length() > 1)
            tailIterator = new PermutationIterator(string.substring(pos + 1));
    }

    public String nextPermutation() {
        if (word.length() == 1) {
            pos++;
            return word;
        } else if (tailIterator.hasMorePermutations()) {
            return currentLetter + tailIterator.nextPermutation();
        } else {
            pos++;
            currentLetter = word.charAt(pos) + "";
            String tailString = word.substring(0, pos) + word.substring(pos + 1);
            tailIterator = new PermutationIterator(tailString);
            return currentLetter + tailIterator.nextPermutation();
        }

    }

    public boolean hasMorePermutations() {
        return pos <= word.length() - 1;
    }
}

现在程序会打印“eat”和“eta”，但之后它会从第二个堆栈中输出一个 StringIndexOutOfBounds 错误。非常感谢任何解决此问题的帮助。

Answer 1

我不只是提供修复程序，还可以帮助诊断您的问题，然后您就可以尝试修复它。

如果仔细查看代码，您会发现当 pos == word.length() - 1 时，hasMorePermutations 条件通过。这意味着当 pos 指向字符串中的最后一个字符时，nextPermutation 将运行。但在这种情况下，当第三个分支执行时，您将递增 pos，然后调用 word.substring(pos + 1)。此时 pos + 1 将大于将引发异常的字符串长度。

我预计修复会相当容易。