有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
思路
暴力法
两层for循环，逐个比较输入的两字符串的所有字母是否是相同的，如果是，则为字母异位词
class Solution {
public boolean isAnagram(String s, String t) {
int count = 0;
for(int i = 0; i < s.length(); i++){
for(int j = 0; j < t.length(); j++){
if(s.charAt(i) == t.charAt(j)){
count++;
}
}
}
if(count == s.length()){
return true;
}else{
return false;
}
}
}
问题：没有考虑相同字母多次出现的情况
目前暴力法的复杂度已经是n*n了，加上相同字母的标记肯定更复杂，很可能超时
应该使用后别的更优的方法去解题
哈希法
要用哈希法，那肯定要选择一种哈希结构来储存数据（区别于简介：详见）
- 数组
- set
- map
选哪种呢？
本题给的数据输入是字符串，且条件是字符串只包含小写字母
也就是a-z，一共26个
除此之外，字母a-z的ASCII码是连续的
小规模连续数据，我们可以考虑用数组来存储
先定义一个长度为26的数组hash
遍历字符串s，记录每个字母出现的次数，并在hash的对应位置累加（就是++）
然后遍历字符串t，记录每个字母出现的次数，并在hash对应位置累减（就是--）
当遍历结束，我们去访问数组的所有元素
如果均为0，那么代表着字符串s中的字母也在字符串t中出现了一遍（因此累加累减相互抵消）
如果出现了不是0的数，那么至少有一方的某个字母多出现几次，则不满足条件
这样就可以判断这个字符串是否为字母异位词
代码
思路大致就是上面的，但是代码实现起来依旧有技巧（感觉每道题都差不多是这样，要么代码有坑要么思路有坑）
class Solution {
public boolean isAnagram(String s, String t) {
int[] hash = new int[26];
for(int i = 0; i < s.length(); i++){
// //获取当前字母所在位置
// //通过与a作差就能够过ASCII码的差值找到当前之母的对应位置
// //例如，a和a相减是ASCII值相减，结果为0，a也就位于字母表0~25的第0个
// int index_s = s.charAt(i) - 'a';
// //对应字母出现次数计数累加
// hash[index_s]++;
//合起来写如下
hash[s.charAt(i) - 'a']++;
}
for(int j = 0; j < t.length(); j++){
// //同理
// int index_t = t.charAt(j) - 'a';
// hash[index_t]--;
hash[t.charAt(j) - 'a']--;
}
//判断hash数组是否全为0
for(int i = 0; i < 26; i++){
if(hash[i] != 0){
return false;
}
}
return true;
}
}
考察点总结
1、定位字母所在位置
这里使用了ASCII码值相减的方法来确定遍历到的字母具体位于0~25的哪里
实现这种方式的前提是：字母的ASCII码是连续的
2、遍历字符串
Java中：
str = "dayceng"
for(int j = 0; j < str.length(); j++){
//使用charAt()来得到字符串中j位置的字母
System.out.println(str.charAt(j));
}
CPP中：
str = "dayceng"
for(int j = 0; j < str.size(); j++){
//直接把字符串当成类似Python中的"列表"来操作即可
cout << str[j] << endl;
}
