题目
题目来源leetcode
leetcode地址：242. 有效的字母异位词，难度：简单。
题目描述(摘自leetcode)：
给定两个字符串 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 仅包含小写字母
本地调试代码：
class Solution { public boolean isAnagram(String s, String t) { ... } public static void main(String[] args) { String s = "anagram"; String t = "anggram"; System.out.println(new Solution().isAnagram(s,t)); } }
题解
NO1：暴力法（O(n2)，超时）
思路：
代码：
public boolean isAnagram(String s, String t) { //字符串长度不相等、为0情况直接返回 if(s == null || t == null || s.length() != t.length() || s.length() == 0){ return false; } for (int i = 0; i < s.length(); i++) { int sNum = 0; char sChar = s.charAt(i); //s字符串获取当前字符的相同个数 for (int j = 0; j < s.length(); j++) { if(sChar == s.charAt(j)){ sNum++; } } //t字符串统计sChar的个数 int tNum = 0; for (int j = 0; j < t.length(); j++) { if(sChar == t.charAt(j)){ tNum++; } } if(tNum !=sNum){ return false; } } return true; }
NO2：哈希法（重点，O(n)）
思路：根据提示s 和 t 仅包含小写字母，所以我们可以直接定义一个大小为26的int数组默认索引值都为0，对应下标0-25存放'a'-'z'的重复次数，之后遍历s、t来进行统计，最终可根据数组中的值是否相等或为0来确定是否为有效的字母异位词。
代码：下面是进行修改了三次，思路都是一致的
//首次看思路自己写代码 public boolean isAnagram(String s, String t) { if(s == null || t == null || s.length()!=t.length() || s.length() == 0){ return false; } //设置两个数组来进行分别记录对应的字符串字符的数量 int[] sArr = new int[26]; int[] tArr = new int[26]; //遍历一遍s for (int i = 0; i < s.length(); i++) { sArr[s.charAt(i)-'a']++; tArr[t.charAt(i)-'a']++; } for (int i = 0; i < 26; i++) { if(sArr[i] != tArr[i]){ return false; } } return true; } //优化一：两个数组=>一个数组 public boolean isAnagram(String s, String t) { if(s == null || t == null || s.length()!=t.length() || s.length() == 0){ return false; } //使用一个数组来进行存储 int[] recordsNumsArr = new int[26]; //长度一致，我们分别来进行+、-操作对数组的某个索引值 for (int i = 0; i < s.length(); i++) { recordsNumsArr[s.charAt(i)-'a']++; recordsNumsArr[t.charAt(i)-'a']--; } //来对记录字符数的数组进行遍历，一旦某个数组索引值!=0说明不有效 for (int i = 0; i < 26; i++) { if(recordsNumsArr[i] != 0){ return false; } } return true; } //优化二：添加提前结束操作 public boolean isAnagram(String s, String t) { if(s == null || t == null || s.length()!=t.length() || s.length() == 0){ return false; } //使用一个数组来进行存储 int[] recordsNumsArr = new int[26]; for (int i = 0; i < s.length(); i++) { recordsNumsArr[s.charAt(i)-'a']++; } for (int i = 0; i < t.length(); i++) { recordsNumsArr[t.charAt(i)-'a']--; //提前结束：一旦在t中的某个字符相同数量>s中的 if(recordsNumsArr[t.charAt(i)-'a'] < 0){ return false; } } //来对记录字符数的数组进行遍历，一旦某个数组索引值!=0说明不有效 for (int i = 0; i < 26; i++) { if(recordsNumsArr[i] != 0){ return false; } } return true; }
用Java执行的话大多数都是需要4ms，我还在想为啥只击败了45%，之后使用c语言的同样逻辑代码测了下过0ms，直接击败100%。
bool isAnagram(char *s, char *t) { int i, x[26] = { 0 }, y[26] = { 0 }; for (i = 0; s[i] != '\0'; i++) x[s[i] - 'a']++; //建立 s 的字符表 x for (i = 0; t[i] != '\0'; i++) y[t[i] - 'a']++; //建立 t 的字符表 y for (i = 0; i < 26; i++) //比较两字符表是否相同 if (x[i] != y[i]) return false; return true; //种类、个数均相同 }
NO3：借助Java的API来解决
//方式一：字符数组排序比对 public boolean isAnagram(String s, String t) { if(s == null || t == null || s.length()!=t.length() || s.length() == 0){ return false; } //思路：字符串s、t转成字符数组，分别进行排序，之后使用Arrays工具类进行比较 char[] sArr = s.toCharArray(); char[] tArr = t.toCharArray(); Arrays.sort(sArr); Arrays.sort(tArr); return Arrays.equals(sArr,tArr); } //方式二：利用map集合解决 public boolean isAnagram(String s, String t) { if(s == null || t == null || s.length()!=t.length() || s.length() == 0){ return false; } Map<Character,Integer> map = new HashMap<>(s.length()); //遍历字符数组s，以key、value进行存储，key设置为字符，value则表示指定的数字 for(char ch : s.toCharArray()){ map.put(ch,map.getOrDefault(ch,0)+1); } //遍历字符数组t for(char ch : t.toCharArray()){ Integer num = map.get(ch); //为null表示没有该数 if(num == null){ return false; }else if(num>1){ map.put(ch,num-1); }else{ //num<=1情况，数量-1即可0，此时我们直接移除即可 map.remove(ch); } } return map.isEmpty(); } //方式三：使用strean public boolean isAnagram(String s, String t) { if(s == null || t == null || s.length()!=t.length() || s.length() == 0){ return false; } int[] numArr = new int[26]; //这里不使用stream是因为若是转为数组还有个copy过程 s.chars().forEach(ch->numArr[ch-'a']++); t.chars().forEach(ch->numArr[ch-'a']--); //直接对数组进行stream流操作 return Arrays.stream(numArr).allMatch(ch->ch == 0); }
