如何处理字谜搜索期间字符串排列的时间复杂度？

Question

我有一个程序可以计算两个字符串是否是变位词。它适用于长度小于 10 的字符串输入。当我输入两个长度相等且长度超过 10 的字符串时，程序运行但没有产生答案。

我的想法是，如果两个字符串是变位词，那么一个字符串必须是另一个字符串的排列。

该程序从一个字符串生成所有排列，然后检查另一个字符串是否有任何匹配的排列。在这种情况下，我想忽略案例。当没有找到匹配的字符串或者比较的字符串长度不相等时returns false，否则returns true.

public class Anagrams {
    static ArrayList<String> str = new ArrayList<>();

    static boolean isAnagram(String a, String b) {
        // there is no need for checking these two
        // strings because their length doesn't match
        if (a.length() != b.length())
            return false;

        Anagrams.permute(a, 0, a.length() - 1);

        for (String string : Anagrams.str)
            if (string.equalsIgnoreCase(b))
                // returns true if there is a matching string
                // for b in the permuted string list of a
                return true;
        // returns false if there is no matching string
        // for b in the permuted string list of a
        return false;
    }

    private static void permute(String str, int l, int r) {
        if (l == r)
            // adds the permuted strings to the ArrayList
            Anagrams.str.add(str);
        else {
            for (int i = l; i <= r; i++) {
                str = Anagrams.swap(str, l, i);
                Anagrams.permute(str, l + 1, r);
                str = Anagrams.swap(str, l, i);
            }
        }
    }

    public static String swap(String a, int i, int j) {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }
}

1.我想知道为什么这个程序不能处理更大的字符串

2.我想知道如何解决这个问题

你能算出来吗？

Answer 1

你正在以非常昂贵的方式进行，并且这里的时间复杂度是指数级的，因为你正在使用需要阶乘和阶乘增长非常快的排列，因为你正在做排列，所以需要时间来获得输出当输入大于 10.

11 factorial = 39916800 12 factorial = 479001600 13 factorial = 6227020800

等等...

所以不要以为你没有得到大数字的输出你最终会得到它

如果你使用 20-30 阶乘之类的东西，我想我将需要数年时间才能产生任何输出，如果你使用循环，则递归会使堆栈溢出。

事实: 50阶乘是一个比地球上沙粒数还多的数，电脑要处理这么大的数就投降了。

这就是为什么他们让你在密码中包含特殊字符，以使排列的数量太大，以至于如果计算机尝试每一种排列，多年都无法破解它，加密也取决于计算机的弱点.

所以你不必也不应该这样做来解决它（因为计算机不是很擅长），这是一个矫枉过正

你为什么不从一个字符串中取出每个字符并将其与另一个字符串的每个字符匹配，在最坏的情况下它会是二次方的。

如果你对两个字符串都进行排序，那么你可以只说

string1.equals(string2)

true 表示 anagram

false 表示 不是字谜

除了排序所花费的时间外，这将花费线性时间。

Answer 2

要解决此问题并检查两个字符串是否是变位词，您实际上不需要生成源字符串的每个排列，然后将其与第二个排列进行匹配。您可以做的是计算第一个字符串中每个字符的频率，然后验证第二个字符串是否具有相同的频率。

上面的解决方案需要每个字符串通过一次，因此时间复杂度为 Θ(n)。此外，您需要辅助存储来计算复杂度为 Θ(1) space 的字符。这些是渐近紧界。

Answer 3

你可以先从这些字符串中得到字符数组，然后sort它们，然后比较两个排序后的数组。此方法适用于 常规字符 和 代理对 .

public static void main(String[] args) {
    System.out.println(isAnagram("ABCD", "DCBA")); // true
    System.out.println(isAnagram("", "")); // true
}

static boolean isAnagram(String a, String b) {
    // invalid incoming data
    if (a == null || b == null
            || a.length() != b.length())
        return false;

    char[] aArr = a.toCharArray();
    char[] bArr = b.toCharArray();

    Arrays.sort(aArr);
    Arrays.sort(bArr);

    return Arrays.equals(aArr, bArr);
}

^{另请参阅：Check if one array is a subset of the other array - special case}

如何处理字谜搜索期间字符串排列的时间复杂度？

How to handle the time complexity for permutation of strings during anagrams search?

java

algorithm

time-complexity

permutation

anagram