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的输入字符串，总共有1125899907E15个不同的字符串可以通过这种方式生成。这比万亿（短期）多一点。或者换句话说：如果每个单词都可以写入一个字节，那么生成的单词仍然会填满1PB

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

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

然而，主要的问题是，输出与输入的大小成指数增长，因此任何算法都会达到机器速度的极限