刷题_有效的字母异位词

发表于2024-04-01更新于2025-09-28阅读次数

内容

原题名叫做：有效的字母异位词。给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。（只包含小写字母）

举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: s = "anagram", t = "nagaram"
输出: true

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

提示:

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

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

即每种字母的数目一样，但是顺序不一定。

分析

若是有限个字母比如26个英文字母，则可以建立一个一维数组S，遍历s，计每种祖母数。然后再建立一个一维数组T，遍历t，计数。最后判断S和T的内容是否一样。

代码

解1_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isAnagram(string s, string t) {
        std::vector<int> vis = std::vector<int>(26);
        std::vector<int> vit = std::vector<int>(26);
        const char * cp = s.c_str();
        while(*cp != '\0')
        {
            ++vis[*cp++ - 'a'];
        }
        cp = t.c_str();
        while(*cp != '\0')
        {
            ++vit[*cp++ - 'a'];
        }
        int i = 0;
        while(i < 26)
        {
            if(vis[i] != vit[i++])
            {
                return false;
            }
        }
        return true;
    }
};

优化

可以不用去创建另外一个数组，而是在遍历t的过程中去减第一个数组中的value，遇到小于零的情况则false。（这已经足够了，不需要去判断第一个数组中是否全部为0了。因为前置条件已经限制两串长度一致，假如2号串中出现1串中不一样的字符，肯定会出现负值。如果2号串的字符种类没有多出来的，而数目多，比如1号串car，2号串raa，则a的值也会出现负值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()) return false;
        if(s.length() == 0) return false;
        std::vector<int> vis = std::vector<int>(26);
        const char * cp = s.c_str();
        while(*cp != '\0')
        {
            ++vis[*cp++ - 'a'];
        }
        cp = t.c_str();
        while(*cp != '\0')
        {
            if(--vis[*cp++ - 'a'] < 0)
            {
                return false;
            }
        }
        return true;
    }
};

坑

解2_hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<unordered_map>
class Solution {
public:
    bool isAnagram(string s, string t) {
        //using std::hash_map<char, int> = CharIntMap;
        if(s.length() != t.length()) return false;
        if(s.length() == 0) return false;
        typedef std::unordered_map<char, int> CharIntMap;
        CharIntMap charIntMap_s;
        const char * cp = s.c_str();
        while(*cp != '\0')
        {
            ++charIntMap_s[*cp++];
        }
        CharIntMap charIntMap_t;
        cp = t.c_str();
        while(*cp != '\0')
        {
            ++charIntMap_t[*cp++];
        }
        for(auto it = charIntMap_s.begin(); it != charIntMap_s.end(); ++it)
        {
            if(charIntMap_t[it->first] != it->second)
            {
                return false;
            }
        }
        return true;
    }
};

心得

这个题目属于

总结