java如何处理字谜搜索过程中字符串排列的时间复杂性？

Question

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

我的概念是，如果两个字符串是字谜，那么一个字符串必须是另一个字符串的排列

这个程序从一个字符串生成所有排列，然后检查另一个字符串是否有匹配的排列。在这种情况下，我想忽略案例。 如果未找到匹配字符串或比较字符串的长度不相等，则返回false，否则返回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

您可以首先从这些字符串中获取字符数组，然后^{}它们，然后比较两个排序的数组。此方法同时适用于常规字符和代理项对

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}

Answer 2

要解决这个问题并检查两个字符串是否是字谜，实际上不需要生成源字符串的每个排列，然后将其与第二个匹配。相反，您可以计算第一个字符串中每个字符的频率，然后验证第二个字符串是否适用相同的频率

上述解决方案要求每个字符串通过一次，因此Θ（n）时间复杂度。此外，还需要辅助存储来计算字符，这是Θ（1）空间复杂度。这些是渐近紧界

Answer 3

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

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

等等

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

如果你做20-30个阶乘，我想我需要几年的时间来产生任何输出，如果你使用循环，递归你会溢出堆栈

事实：50阶乘是一个非常大的数字，它比地球上的沙粒数量还要多，当他们不得不处理这么大的数字时，计算机就会投降

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

因此，您不必也不应该这样做来解决它（因为计算机并不擅长于此），这是一种过激的行为

为什么不把一个字符串中的每一个字符和另一个字符串中的每一个字符进行匹配呢？在最坏的情况下，它将是二次的

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

string1.equals(string2)

true表示字谜

false表示不是字谜

它将需要线性时间，除了排序所需的时间