LCR 032-有效的字母异位词

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给定两个字符串 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 * 104
  • s and t 仅包含小写字母

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

注意：本题与主站 242 题相似（字母异位词定义不同）：https://leetcode-cn.com/problems/valid-anagram/

方法一：排序

t 是 s 的变位词等价于「两个字符串不相等且两个字符串排序后相等」。首先判断字符串 s 和 t 是否相等，如果相等则直接返回 false，如果不相等则继续判断两个字符串排序后是否相等。我们可以对字符串 s 和 t 分别排序，看排序后的字符串是否相等。此外，如果 s 和 t 的长度不同，t 必然不是 s 的变位词。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}
[sol1-JavaScript]
1
2
3
var isAnagram = function(s, t) {
    return s.length == t.length && s !== t && [...s].sort().join('') === [...t].sort().join('')
};
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length() || s == t) {
            return false;
        }
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
func isAnagram(s, t string) bool {
    if s == t {
        return false
    }
    s1, s2 := []byte(s), []byte(t)
    sort.Slice(s1, func(i, j int) bool { return s1[i] < s1[j] })
    sort.Slice(s2, func(i, j int) bool { return s2[i] < s2[j] })
    return string(s1) == string(s2)
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int cmp(const void* _a, const void* _b) {
    char a = *(char*)_a, b = *(char*)_b;
    return a - b;
}

bool isAnagram(char* s, char* t) {
    int len_s = strlen(s), len_t = strlen(t);
    if (len_s != len_t || strcmp(s, t) == 0) {
        return false;
    }
    qsort(s, len_s, sizeof(char), cmp);
    qsort(t, len_t, sizeof(char), cmp);
    return strcmp(s, t) == 0;
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 为 s 的长度。排序的时间复杂度为 O(n\log n)，比较两个字符串是否相等时间复杂度为 O(n)，最多需要执行两次字符串比较，因此总体时间复杂度为 O(n \log n+2n)=O(n\log n)。

  • 空间复杂度：O(\log n)。排序需要 O(\log n) 的空间复杂度。注意，在某些语言（比如 Java & JavaScript）中字符串是不可变的，因此我们需要额外的 O(n) 的空间来拷贝字符串。但是我们忽略这一复杂度分析，因为：

    • 这依赖于语言的细节；
    • 这取决于函数的设计方式，例如，可以将函数参数类型更改为 char[]。

方法二：哈希表

从另一个角度考虑，t 是 s 的变位词等价于「两个字符串不相等且两个字符串中字符出现的种类和次数均相等」。首先判断字符串 s 和 t 是否相等，如果相等则直接返回 false，如果不相等则继续比较两个字符串中字符出现的种类和次数。由于字符串只包含 26 个小写字母，因此我们可以维护一个长度为 26 的频次数组 table，先遍历记录字符串 s 中字符出现的频次，然后遍历字符串 t，减去 table 中对应的频次，如果出现 table}[i]<0，则说明 t 包含一个不在 s 中的额外字符，返回 false 即可。

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var isAnagram = function(s, t) {
    if (s.length !== t.length || s == t) {
        return false;
    }
    const table = new Array(26).fill(0);
    for (let i = 0; i < s.length; ++i) {
        table[s.codePointAt(i) - 'a'.codePointAt(0)]++;
    }
    for (let i = 0; i < t.length; ++i) {
        table[t.codePointAt(i) - 'a'.codePointAt(0)]--;
        if (table[t.codePointAt(i) - 'a'.codePointAt(0)] < 0) {
            return false;
        }
    }
    return true;
};
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length() || s == t) {
            return false;
        }
        vector<int> table(26, 0);
        for (auto& ch: s) {
            table[ch - 'a']++;
        }
        for (auto& ch: t) {
            table[ch - 'a']--;
            if (table[ch - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
func isAnagram(s, t string) bool {
    if s == t {
        return false
    }
    var c1, c2 [26]int
    for _, ch := range s {
        c1[ch-'a']++
    }
    for _, ch := range t {
        c2[ch-'a']++
    }
    return c1 == c2
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isAnagram(char* s, char* t) {
    if (len_s != len_t || strcmp(s, t) == 0) {
        return false;
    }
    int table[26];
    memset(table, 0, sizeof(table));
    for (int i = 0; i < len_s; ++i) {
        table[s[i] - 'a']++;
    }
    for (int i = 0; i < len_t; ++i) {
        table[t[i] - 'a']--;
        if (table[t[i] - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

对于进阶问题，Unicode 是为了解决传统字符编码的局限性而产生的方案，它为每个语言中的字符规定了一个唯一的二进制编码。而 Unicode 中可能存在一个字符对应多个字节的问题，为了让计算机知道多少字节表示一个字符，面向传输的编码方式的 UTF}-8 和 UTF}-16 也随之诞生逐渐广泛使用，具体相关的知识读者可以继续查阅相关资料拓展视野，这里不再展开。

回到本题，进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。同时读者需要注意 Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。

[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        Map<Character, Integer> table = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) - 1);
            if (table.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }
}
[sol3-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func isAnagram(s, t string) bool {
    if len(s) != len(t) || s == t {
        return false
    }
    cnt := map[rune]int{}
    for _, ch := range s {
        cnt[ch]++
    }
    for _, ch := range t {
        cnt[ch]--
        if cnt[ch] < 0 {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 s 的长度。

  • 空间复杂度：O(S)，其中 S 为字符集大小，此处 S=26。

 Comments
On this page
LCR 032-有效的字母异位词