目录

题目

思路

代码 

---

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

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

思路

1.什么是异位词？

两个字符串中除了字母的顺序不一样以外，组成字符串的字母都一样。

2.怎么想到要使用哈希表？

相当于查找一个字母是否在集合中，自然想到哈希表。

3.暴力解法可否解出来？

用两个for循环，可以暴力解出来，时间复杂度是O（n^2）

4.用哈希表的思路

• 关键是构造哈希函数，想到用一个数组存每个字母出现的次数，将出现的字母种类称作a，哈希表的长度称作b a不能大于b，特殊之处在于，是字母，且两个字符串都是小写的，a-z的ASCII码差为26，所以创建一个长度为26的就可以。
• 先遍历一个字符串S，通过某种方式，找到存他的位置，出现一次位置上就+1，通过这种方法来得到他出现几次
• 通过的方式：长度为26，所以数组必然是从0-25，只需要用得到的字母的ASCII码减去a的，就可以得到唯一确定的存储位置。
• 接着遍历另一个字符串T，通过同样的方式找到唯一存储的位置索引，然后-1
• 最后只需要遍历哈希表，如果所有元素都为0，那么返回true，否则不行（如果大于0，说明某个字母在S中出现比在T中多出现一次，如果小于0说明某个字母在T中比在S中多出现一次）

代码 

class Solution {public boolean isAnagram(String s, String t) {int[] c=new int[26];//创建长度为26的哈希表，让每个字母出现的次数都有唯一且确定的位置存放for(int i=0;i<s.length();i++){//遍历其中一个字符串c[s.charAt(i)-'a']++;//找到存放的位置，出现次数+1}for(int j=0;j<t.length();j++){//遍历另一个元素c[t.charAt(j)-'a']--;}for(int result:c){//遍历哈希表if(result!=0){return false;//不是}}  return true;//是} 
}

class Solution {public boolean isAnagram(String s, String t) {if(s.length() != t.length())//长度不一样，必然不是return false;int[] alpha = new int[26];for(int i = 0; i< s.length(); i++) {//有了上述判断只需要遍历一个字符串就可以了alpha[s.charAt(i) - 'a'] ++;alpha[t.charAt(i) - 'a'] --;}for(int i=0;i<26;i++)if(alpha[i] != 0)return false;return true;}
}