题目:
给定两个字符串 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
创新互联专注为客户提供全方位的互联网综合服务,包含不限于成都网站制作、做网站、德钦网络推广、小程序开发、德钦网络营销、德钦企业策划、德钦品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联为所有大学生创业者提供德钦建站搭建服务,24小时服务热线:13518219792,官方网址:www.cdcxhl.com
对于这样的题,解题思路是:
在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
2.map的解法
()
bool isok(string s, string t) {
if(s.size() != t.size()) return false;
map MAP;
for(int i = 0; i
};
对第二种解法的补充:
首先我们介绍一下两种编码 **
1.最开始的ASCII--对应了英语字符和二进制的关系
2.后来为了改进,将世界上所有的字符都给包含进去的Unicode**
通过这样的介绍,可以知道如果按照第一种解法来做,那么局限性就很大了,编码的不足够,虽然在这种简单的题上,数组模拟(4ms)确实更快(map 20ms),但是不是通用,所以按需选择吧。