有效的字母异位词[简单]

分手后的思念是犯贱 2024-02-20 12:45 10阅读 0赞

优质博文：[IT-BLOG-CN][]

### 一、题目 ###

给定两个字符串`s`和`t`，编写一个函数来判断`t`是否是`s`的字母异位词。注意：若`s`和`t`中每个字符出现的次数都相同，则称`s`和`t`互为字母异位词。

**示例 1:**  
输入: `s = "anagram", t = "nagaram"`  
输出: `true`

**示例 2:**  
输入: `s = "rat", t = "car"`  
输出: `false`

> `1 <= s.length, t.length <= 5 * 104`  
> `s`和`t`仅包含小写字母 :::

**进阶:** 如果输入字符串包含`unicode`字符怎么办？你能否调整你的解法来应对这种情况？

> `Unicode`是为了解决传统字符编码的局限性而产生的方案，它为每个语言中的字符规定了一个唯一的二进制编码。而`Unicode`中可能存在一个字符对应多个字节的问题，为了让计算机知道多少字节表示一个字符，面向传输的编码方式的`UTF−8`和`UTF−16`也随之诞生逐渐广泛使用

### 二、代码 ###

**【1】哈希表：** 我们用**哈希表**维护对应字符的频次即可。需要注意`Unicode`一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            if (s == null || t == null || s.length() != t.length()) {
        
                return false;
            }
            // 思想：创建1个hashMap存储s的字符为key，value为字符的个数，最后遍历t，对value进行递减，如果小于0则为false;
            Map<Character,Integer> map = new HashMap();
            for (int i = 0; i < s.length(); i++) {
        
                map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            }
            for (int i = 0; i < t.length(); i++) {
        
                int count = map.getOrDefault(t.charAt(i), 0) - 1;
                if (count < 0) {
        
                    return false;
                }
                map.put(t.charAt(i), count);
            }
            return true;
        }
    }

**时间复杂度：** `O(n)`其中`n`为`s`的长度。  
**空间复杂度：** `O(S)`其中`S`为字符集大小，此处`S=26`。

**【2】一维数组：** 如果不考虑`Unicode`时，字符串只包含`26`个小写字母，因此我们可以维护一个长度为`26`的一维数组`table`，先遍历记录字符串`s`中字符出现的频次，然后遍历字符串`t`，减去`table`中对应的频次，如果出现`table[i]<0`，则说明`t`包含一个不在`s`中的额外字符，返回`false`即可。

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            if (s == null || t == null || s.length() != t.length()) {
        
                return false;
            }
            // 维护一个长度为26的一维数组，并将s字符维护进去
            int[] arr = new int[26];
            for (int i = 0; i < s.length(); i++) {
        
                arr[s.charAt(i) - 'a']++;
            }
            // 遍历t字符串，进行count--
            for (int i = 0; i < t.length(); i++) {
        
                arr[t.charAt(i) - 'a']--;
                if (arr[t.charAt(i) - 'a'] < 0) {
        
                    return false;
                }
            }
            return true;
        }
    }

**时间复杂度：** `O(n)`其中`n`为`s`的长度。  
**空间复杂度：** `O(S)`其中`S`为字符集大小，此处`S=26`。

**【3】字符排序：** `t`是`s`的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串`s`和`t`分别排序，看排序后的字符串是否相等即可判断。此外，如果`s`和`t`的长度不同，`t`必然不是`s`的异位词。

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            if (s == null || t == null || s.length() != t.length()) {
        
                return false;
            }
            // 投机法：对两个字符串排序后，判断是否相等
            char[] s1 = s.toCharArray();
            char[] t1 = t.toCharArray();
    
            // 排序
            Arrays.sort(s1);
            Arrays.sort(t1);
    
            // 判断是否相等
            return Arrays.equals(s1,t1);
        }
    }

**时间复杂度：** `O(nlog⁡n)`，其中`n`为`s`的长度。排序的时间复杂度为`O(nlog⁡n)`，比较两个字符串是否相等时间复杂度为`O(n)`，因此总体时间复杂度为`O(nlog⁡n+n)=O(nlog⁡n)`。  
**空间复杂度：** `O(log⁡n)`。排序需要`O(log⁡n)`的空间复杂度。注意，在某些语言（比如`Java & JavaScript`）中字符串是不可变的，因此我们需要额外的`O(n)`的空间来拷贝字符串。但是我们忽略这一复杂度分析，因为：这依赖于语言的细节；这取决于函数的设计方式，例如，可以将函数参数类型更改为`char[]`。

[IT-BLOG-CN]: https://it-blog-cn.com/blogs/algorithm/topic/easy/effective_words.html