java - 字符串字谜的边界条件

Question

我试图编写一个字符串 Anagram 程序，但在检查边界条件时卡住了。

我知道互联网上有很多与使用单循环或使用集合框架的字符串字谜相关的方法和程序，但我需要我的代码的解决方案，即如何涉​​及代码的边界情况。

public class StringAnagram {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    String str = "abc";
    String strAnagram = "cba";

    boolean areAnagrams = ifAnagrams(str, strAnagram);
    System.out.println(areAnagrams);
}

private static boolean ifAnagrams(String str, String strAnagram) {
    // TODO Auto-generated method stub

    int count = 0;
    char[] a = strAnagram.toCharArray();

    if (str.length() != strAnagram.length()) {
        return false;
    }

    for (int i = 0; i < str.length(); i++) {
        {
            System.out.println("str.charAt(i) in outer loop :" + str.charAt(i));

            for (int j = 0; j < strAnagram.length(); j++) {
                if (str.charAt(i) == strAnagram.charAt(j)) {
                    System.out.println("str.charAt(i) : " + str.charAt(i));
                    System.out.println("strAnagram.charAt(j) : " + strAnagram.charAt(j));

                    count++;
                }
            }
        }
        System.out.println(count);
        if (count == str.length()) {
            return true;
        }
    }

    return false;
}
}

如果我输入像这样的输入，代码就可以正常工作 -“abc”或“abcd”，其中字符串中的每个字符仅出现一次，但当输入类似于“aab”时会失败，可以将“abc”与“abc”进行比较，并且会显示字符串是字谜词。那么，我如何在我的代码中处理这种情况。请指教。

Answer 1

您的解决方案的问题在于它仅检查第一个字符串中的每个字符是否存在于第二个字符串中。您还需要考虑 2 个条件:

1. 如果第二个字符串中的每个字符也出现在第一个字符串中
2. 如果第一个和第二个字符串中每个字符的字符数匹配

对于输入 ("aaa", "abc")，您当前的解决方案将返回 True，而应返回 False。实现我上面提到的第一个条件将解决这个问题。

实现第一个条件后，您的解决方案对于输入 ("abb", "aab") 将返回 True，而应返回 False。实现我上面提到的第二个条件将解决这个问题。

这是实现此目的的简单方法:

Map<Character, Integer> charCount = new HashMap<Character, Integer>();

for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    if (charCount.containsKey(c)) {
        charCount.put(c, charCount.get(c)+1);
    } else {
        charCount.put(c, 1);
    }
}

for (int i = 0; i < strAnagram.length(); i++) {
    char c = strAnagram.charAt(i);
    if (!charCount.containsKey(c)) return false;
    if (charCount.get(c) == 0) return false;
    charCount.put(c, charCount.get(c)-1);
}

for (char k : charCount.keySet()) {
    if (charCount.get(k) != 0) return false;
}

return true;

由于没有嵌套循环，时间复杂度为O(n)。即使使用Map，空间复杂度也是O(1)，因为可以保证键的总数不会超过所有可能字符的数量。

这个解决方案在时间和空间复杂度方面甚至比排序更好。