Anagram检查实现

Question

给定两个字符串时，检查两个给定字符串是否彼此相联。字符串的字元是另一个包含相同字符的字符串，只有字符的顺序可以不同。例如，“act”和“tac”是彼此的对白。输入：输入的第一行包含表示测试用例数量的整数T。每个测试用例只包含两个‘小写’字符串，在一个单独的行中。输出：如果两个字符串是anagram，则打印没有引号的"YES“，否则打印"NO”。约束条件：1≤T≤30 1≤S≤100 示例：输入：2极健忘型健忘型健忘症过敏输出：是否

我的方法：

/*package whatever //do not write package name here */

import java.util.Scanner;
import java.io.IOException;
import java.util.HashMap;

class GFG {

    private static String isAnagram (String str1, String str2)
        {
            HashMap occurs = new HashMap<>();

            if (str1.length() != str2.length())
                {
                    return "NO";
                }

            for (char ch: str1.toCharArray())
                {
                    if (!(occurs.containsKey(ch)))
                        {
                            occurs.put(ch,1);
                        }
                    else
                        {
                            int count = occurs.get(ch);
                            occurs.put(ch,count + 1);
                        }
                }

            for (char ch: str2.toCharArray())
                {
                    if (!(occurs.containsKey(ch)))
                        {
                            return "NO";
                        }
                    else
                        {
                            int count = occurs.get(ch);
                            count  = count - 1;
                            if (count < 0)
                                {
                                    return "NO";
                                }
                            else
                                {
                                    occurs.put(ch,count);
                                }
                        }
                }

        return "YES";    
        }

    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner (System.in);
        int numTests = sc.nextInt();

        for (int i = 0; i < numTests; i++)
            {
                String str1 = sc.next();
                String str2 = sc.next();
                System.out.println(isAnagram(str1, str2));
            }
    }
}

我对上述守则有以下问题：

( 1)如何进一步改善我的做法？

( 2)是否有更好的方法来解决这个问题？

( 3)我是否有严重违反守则的行为？

( 4)空间和时间复杂度能否进一步提高？

参考文献

Answer 1

使用HashMap使用计数系统是解决问题的一种功能方法，从算法上看，它比较好(时间复杂度为\O(N)\n)。但是，对于像这样的问题，将每个输入值规范化为排序数组或字符串比在计数HashMap中更容易。

考虑以下职能：

public static final String normalize(value) {
    if (value == null) {
        return null;
    }
    char[] chars = value.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

现在，所有作为字谜的值都具有相同的normalize结果(它们具有相同的排序顺序)。

您的代码将简单地变成：

private static String isAnagram (String str1, String str2) {
    return Objects.equals(normalize(str1), normalize(str2));
}

请注意，在本例中，Objects是java.util.Objects。

此外，通过将规范化放入一个单独的函数中，可以减少代码中的逻辑重复。

现在，你问是否有严重的违规行为.我必须回答“是”。在Java中，将{大括号放在与代码块定义相同的行上是常见的做法。例如，您的代码：

for (char ch: str1.toCharArray()) { if (!(occurs.containsKey(ch))) { occurs.put(ch,1); } else { int count = occurs.get(ch); occurs.put(ch,count + 1); } }

应：

        for (char ch: str1.toCharArray()) {
            if (!(occurs.containsKey(ch))) {
                occurs.put(ch,1);
            } else {
                int count = occurs.get(ch);
                occurs.put(ch,count + 1);
            }
        }