异位表达和过表达（有效字母异位词）

题目：

给定两个字符串 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仅包含小写字母

来源：力扣（Lee

tCode）

链接：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）          ，但是不是通用

 
  
 
  
 
  
 
  
 
  
 ，所以按需选择吧 
   
   
   
   
   。