有效的Anagram -LeetCode Java解决方案-DEV365 开发者社区

您好读者，让我们现在解决一个leetcode问题。

在此博客中，让我们解决Valid Anagram，它是Blind 75 List of LeetCode Problems。

对于初学者来说，这是一个非常好的leetcode简单问题。

这个问题有多种潜在解决方案，我们将在此博客中通过。

了解问题

anâ anagram 是通过重新排列另一个单词或短语的字母而形成的单词或短语，通常完全使用所有原始字母。
给定两个字符串sâ和t：
- 返回trueâ，如果tâ是 s的字词
- 返回falseâ否则。

了解测试用例

示例1：

Input: s = "anagram", t = "nagaram"
Output: true

输入字符串 - Anagram”和“ nagaram”完全包含3 -a，1-gâ，1--mâmâ，1-和1-râ。
所以，可以通过重新排列字母来形成“ nagaram”。因此，它们俩都是彼此的字词。

示例2：

Input: s = "rat", t = "car"
Output: false

字符串不包含字符串s的字符：

蛮力方法：排序

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        Arrays.sort(sc);
        Arrays.sort(tc);
        if(new String(sc).equals(new String(tc)))
            return true;
        return false;
    }
}

关键点：

上面的代码检查是否将两个字符串， s 和 t 检查是字符，是通过将它们转换为字符阵列，按上升顺序对数组进行排序，然后比较排序的排序平等的数组。
如果字符的排序阵列相等，则意味着字符串具有相同频率的相同字符，表明它们是彼此的字眼。
代码返回 true 如果字符串是字符词， false 否则。

时间复杂性：O（n log n）

上述代码的时间复杂性为O（n log n），其中n是 s 和 t 之间的较长字符串的长度。这是因为代码使用 Arrays.sort() 对字符数组进行排序 sc 和 tc 。
在平均情况下， Arrays.sort() 方法的时间复杂性为O（n log n）。因此，整体时间复杂性由分类操作主导。

空间复杂性：o（n）

代码的空间复杂性为o（n），其中n是 s 和 t 。
这是因为代码创建了两个字符数组， sc 和 tc ，它存储了输入字符串的字符。
每个字符阵列的长度等于相应输入字符串的长度。因此，字符阵列所需的空间与较长的字符串的长度成正比。

更好的方法：使用两个哈希图计数

class Solution {
    public boolean isAnagram(String s, String t) {
        HashMap<Character, Integer> count1 = new HashMap<>();
        HashMap<Character, Integer> count2 = new HashMap<>();
        count1 = count(count1, s);
        count2 = count(count2, t);
        return count1.equals(count2) ? true : false;
    }
    public HashMap<Character, Integer> count(HashMap<Character, Integer> count, String str) {
        for(int i=0; i<str.length(); i++) {
            Character c=str.charAt(i);
            if(count.containsKey(c)) {
                count.put(c, count.get(c)+1);
                continue;
            }
            count.put(c, 1);
        }
        return count;
    }
}

关键点：

hashmaps count1和count2分别用于计算给定的两个字符串中的字符数量s和t。
函数count()用于穿越给定的字符串，计算字符的出现数并将其存储在count哈希玛普中并返回。
最后，比较了count1和count2，以使给定的两个字符串互相验证是否相互验证。

时间复杂性：o（n）

给定代码的时间复杂性是O（n），其中n是两个字符串中的字符总数。这是因为在 count() 方法中构建频率计数时，代码一次迭代了字符串中的每个字符。
由于 count() 方法被称为两次，每一个输入字符串一次，总时间复杂度为o（x + y），其中x和y是输入字符串的长度 s 和 t 。
但是，由于我们通常会忽略恒定因素，而要关注主要术语，因此将时间复杂性简化为o（n）。

空间复杂性：O（1）或常数

代码的空间复杂性为o（k），其中k是两个字符串中唯一字符的数量。
在最坏的情况下，字符串中的每个独特字符将作为键存储在 count1 和 count2 哈希图中。因此，哈希图所需的空间与唯一字符的数量成正比。
由于唯一字符的总数通常比字符串的长度小得多，因此我们可以认为空间复杂性为O（1）或常数。

最佳方法：使用频率数组计数

public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] alphabet = new int[26];
        for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
        for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
        for (int i : alphabet) if (i != 0) return false;
        return true;
    }
}

关键点：

在上面的代码中，大小26 int数组：alphabet是为字母内每个字母的频率数组创建的。 alphabet的索引代表了字母的26个字母。因此，0代表1代表，直到25代表Z
然后，我们计算字符的频率：
- 我们为第一个迭代中的字符串s字符的每个字符的alphabet数组值递增。
- 然后在第二个迭代中使用字符串t降低相同的alphabet数组的值。
- 在这两个迭代中，我们都执行操作s.charAt(i) - 'a'和t.charAt(i) - 'a'。在这里，字符串s和string t的字符与字符‘a’减去，以获取与alphabet数组相对应的字母的整数值。
如果它们是Anagram，则alphabet桶应保留为零数组的初始值。
所以，最终迭代只会检查所有值是否为零，如果任何值不是零，我们返回false并返回true

时间复杂性：o（n）

上述代码的时间复杂性为o（n），其中n是 s 和 t 之间的较长字符串的长度。这是因为代码仅使用两个单独的循环在两个字符串中仅在两个字符串中迭代。
第一个循环计算字符串中字符的出现 s ，第二个循环减去字符串中字符的出现 t 。最后，有一个第三个循环检查 alphabet 数组中的任何计数是否非零，表明两个字符串之间的字符数不匹配。