java - 通过删除一个或多个字符生成唯一的字符串

Question

我正在尝试生成所有唯一 字符串，这些字符串可以通过从原始字符串中删除一个或多个字符来创建。

例如，对于原始字符串“anna”，生成的字符串将为 nna|ana|ann|na|aa|nn|an|a|n。我不是简单地寻找唯一的子字符串，例如“aa”不是“anna”的子字符串，但它包含在我要查找的字符串集中。

下面的代码生成了正确的结果，但是当原始字符串特别长(例如 50 个字符左右)时速度太慢。我正在寻找有关如何提高效率的建议。

public class Permutation3 {

    private static Set<String> hs = new HashSet<>();

    public static void main(String[] args) {
        perm("ANNA", 0);
        System.out.println(hs.size() - 2);
    }

    private static void perm(String string, int startIndex) {

        hs.add(string);
        for (int i = startIndex; i <= string.length() - 1; i++) {
            StringBuilder sb = new StringBuilder(string);
            sb.deleteCharAt(i);
            perm(sb.toString(), i);

        }
    }

Answer 1

首先:从长度为 n 的字符串中任意删除字符可以产生多少个可能的字符串？

我们可以用长度为 n 的位域来表示每个可以通过这种方式生成的 String，其中每一位表示某个字符是否已被删除。或者换句话说:可以通过这种方式生成 2^n 个可能的字符串。

因此对于长度为 50 的输入字符串，总共可以生成 1,125899907E15 个不同的字符串。这比一千万亿多一点(小规模)。或者换句话说:如果每个字都可以写入一个字节，那么生成的字仍然会填满 1PB。

因此，实际问题不在于性能，而在于将生成的大量值。

当然可以稍微调整一下代码:
例如，递归非常昂贵，您的代码会多次生成某些解决方案。

然而，主要问题是输出与输入大小呈指数增长，因此任何算法都将很快达到您的机器能够达到的极限。