博客

有效字母异位词

  • Post category:C++

题目：
给定两个字符串 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 仅包含小写字母
 
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-anagram

对于这样的题，解题思路是：
在s中寻找构成t的每个字符是否存在

1.特殊情况：如果两者不相等，那么就不可能互为异位词
2.通常情况：如果两者相等，就需要对S中每个元素在t中寻找

假如S中有n个元素，t中有n个元素，那么就需要n*n次查找。（暴力的直接找）
对于这种的需要查找匹配的我可以考虑使用map,C++中STL的map是使用树来做查找算法的。
原因：
1）用A B C等作为index不好进行查找。
2）顺序查找比较慢，效率低。

为了解决 1）
我们可以用数组解决—-把字符转为数组下标作为index
（原理是：通过一个函数（字符-‘a’）就转为index）
这样的话其实和我们的哈希就对应上了，所以说数组就是一个简单的哈希表。

bool isok(string s, string t)   {

int ha[26]={0};
for(int i=0;i<s.size();i++)
ha[s[i]-'a']++;
for(int j=0;j<t.size();j++)
ha[t[j]-'a']--;
for(int i=0;i<26;i++)
if(ha[i]!=0)
return false;

return true;
}//这个相对于暴力解法O(n*n)来说，时间复杂度只有O(n)

2.map的解法
（）

bool isok(string s, string t) {
    if(s.size() != t.size()) return false;
    map<char,int> MAP;
    for(int i = 0; i<s.size(); i++){
        MAP[s[i]] ++;
    }

    for(int i = 0; i<t.size(); i++){
        MAP[t[i]] --;
        if(MAP[t[i]] < 0) return false;
    }
    return true;

}

};
对第二种解法的补充：
首先我们介绍一下两种编码 **
1.最开始的ASCII–对应了英语字符和二进制的关系
2.后来为了改进，将世界上所有的字符都给包含进去的Unicode**
通过这样的介绍，可以知道如果按照第一种解法来做，那么局限性就很大了，编码的不足够，虽然在这种简单的题上，数组模拟（4ms）确实更快（map 20ms），但是不是通用，所以按需选择吧。

Tags: