一尘不染

生成字符串所有组合的算法

java

我在网上找到了一个链接,该链接显示了一种算法来生成字符串的所有组合:http : //www.mytechinterviews.com/combinations-of-a-
string

算法复制如下。

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        System.out.println(outstr);
        combine(instr, outstr, i + 1);
        outstr.deleteCharAt(outstr.length() - 1);
    }
}

combine("abc", new StringBuffer(), 0);

我不明白的是这行:

outstr.deleteCharAt(outstr.length() - 1);

如果我删除此行,则该程序显然不再起作用,但是为什么首先需要这样做?我了解递归的想法,在这个想法中,我们改变了初始字符,然后对其余字符进行了递归,但是deleteChar行似乎在逻辑上不适合任何地方。添加outstr.deleteCharAt行的原因是什么?


阅读 170

收藏
2020-12-03

共1个答案

一尘不染

呼叫outstr.deleteCharAt计数器会outstr.append删除的最后一个字符,以抵消的影响outstr

每个循环的迭代过程如下:

  1. 追加一个字符
  2. 打印结果
  3. 在该级别执行递归调用 i+1
  4. 删除我们在步骤1中添加的字符
2020-12-03