如何处理字符串置换的时间复杂度？

Question

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

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

此程序从一个字符串生成所有排列，然后检查其他字符串是否有匹配的排列。在这种情况下，我想忽略情况。当找不到匹配的字符串或比较字符串的长度不相等时，它返回false；否则返回true。

public class Anagrams {

static ArrayList<String> str=new ArrayList<>();

static boolean isAnagram(String a, String b) {


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

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

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

return false;  //returns false if there is no matching string for b in the permuted string list of a

}


 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

我想知道如何解决此问题

你能弄清楚吗？

我有一个程序可以计算两个字符串是否是字谜。当输入长度小于10的字符串时，它的效果很好。当我输入两个长度相等且长度为...的字符串时...

Answer 1

您正在以非常昂贵的方式进行操作，并且这里的时间复杂度是指数级的，因为阶乘增长非常快，当您进行置换时，输入大于10时将需要一些时间来获得输出。

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

依此类推，如果您使用20-30阶乘，我认为我将需要数年的时间才能产生任何输出，如果您使用循环，则使用递归将使堆栈溢出

Answer 2

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