Java每日一题——＞剑指 Offer II 032. 有效的变位词

• 题目
• 题解1（数组)
• • 代码实现
  • 复杂度分析
• 题解2(哈希表)
• • 代码实现
  • 复杂度分析

这是LeetCode上的 [032，有效的变位词]，难度为 [简单]

给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。

注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

示例 3:

输入: s = "a", t = "a"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 10⁴
• s and t 仅包含小写字母

根据题意，需要算出两个字符串中的每个字符出现的次数，然后比较它们同个字符出现的次数是否相等，若不相等，则不是是变位词

如果只考虑字符串中字符只包含英文小写字符的情况，可以声明一个容量为26的频次数组来存放字符串中每个字符出现的次数，索引为0的位置存放a出现的次数

那怎么算出每个字符需要放在那个索引呢？由于每个字符都有对应的unicode编码，对应int整数，因此可以把每个字符减去字符a就可以得到它在数组中得索引，例如当字符为a时，则a - a = 0，即索引为0,存放在数组的第一个位置

class Solution {
   public boolean isAnagram(String str1, String str2) {
        
        if (str1.length() != str2.length() || str1.equals(str2)) {
            return false;
        }
        // 创建一个频次数组，存放每个字符出现的次数
        int[] counts = new int[26];
        // 字符串转化位char数组
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        // 遍历第一个char型数组，统计每个字符出现的次数
        for (char ch : chars1) {
            counts[ch - 'a']++;
        }
        // 遍历第二个char型数组，
        for (char ch : chars2) {
            
            if (counts[ch - 'a'] == 0) {
                return false;
            }
            // 若频次数组中当前字符出现的次数不为0,则把当前字符的次数减1
            counts[ch - 'a']--;
        }
        return true;
    }
}

假设字符串的长度为n

时间复杂度:

需要遍历两个字符串，故时间复杂度为O(n) + O(n) = 2O(n) = O(n)

空间复杂度:

由于频次数组是容量是固定的，故空间复杂度为O(1)

如果字符串中字符不只包含英文字符时，例如包含中文，日文等其他字符，则可以使用java中哈希表HashMap作为频次数组，HashMap会随着字符串中不同字符的数目增多而扩容

class Solution {
   public boolean isAnagram(String str1, String str2) {
     if (str1.length() != str2.length() || str1.equals(str2)) {
            return false;
        }
        // 创建哈希表作为频次数组
        HashMap counts = new HashMap<>();
        for (char ch : str1.toCharArray()) {
            
            counts.put(ch, counts.getOrDefault(ch, 0) + 1);
        }
        for (char ch : str2.toCharArray()) {
            
            if (!counts.containsKey(ch) || counts.get(ch) == 0) {
                return false;
            }
            // 哈希表(频次数组)当前字符出现的次数大于0,则把当前字符出现次数减一
            counts.put(ch, counts.get(ch) - 1);
        }
        return true;
    }
}

假设两个字符串的长度为n

时间复杂度

需要链表两个字符串，故时间复杂度为O(n)

空间复杂度

哈希表会随着字符串中不同字符个数的增多而扩容，假设不同字符的个数为K，则空间复杂度为O(k)