题目链接
LeetCode-242. 有效的字母异位词
题目描述
题解
题解一（Java）
作者：@仲景
首先，满足条件的情况下，两个字符串的长度一定是相等的，不相等一定不满足条件
使用Hash表来存储字符串s中各个字符出现的次数
遍历字符串t，查看每个字符在hash表中出现的次数，如果次数>0，就减1，如果≤0，说明次数已经没有了（或者没存在过），那么两个字符串一定是不满足条件的，直接返回false
如果遍历完字符串t都没有返回false，那么一定满足条件，直接返回true
时间复杂度：O(N)
空间复杂度：O(N) ，N为字符串s中不同字符的个数
class Solution {public boolean isAnagram(String s, String t) {// 长度不一样就一定不是if (s.length() != t.length())return false;// 创建一个hash表HashMap<Character, Integer> map = new HashMap<>();// 遍历字符串s并添加到hash表中for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);map.put(c, map.getOrDefault(c, 0) + 1);}// 遍历字符串t，查找在hash表中不存在的字符for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);// 获取c在hash表中出现的次数Integer count = map.getOrDefault(c, 0);// 如果不存在，则直接返回falseif (count <= 0)return false;elsemap.put(c, count - 1);}// 全部存在，返回truereturn true;}
}
题解二（Java）
作者：@仲景
因为题目说明字符串中只有小写字母，所以只需要一个26空间的数组就可以代替hash表来存储字符串中各个字符出现的次数
原理和题解一是一样的
时间复杂度：和题解一相同
空间复杂度：O(N)，N=26
class Solution {public boolean isAnagram(String s, String t) {// 长度不一样就一定不是if (s.length() != t.length())return false;// 创建一个26位的数组int[] arr = new int[26];// 遍历字符串sfor (int i = 0; i < s.length(); i++) {arr[s.charAt(i) - 'a']++;}// 遍历字符串tfor (int i = 0; i < t.length(); i++) {arr[t.charAt(i) - 'a']--;if (arr[t.charAt(i) - 'a'] < 0)return false;}return true;}
}
