一、有效的字母异位词
题目链接：242.有效的字母异位词
/** * <pre> * 异位词等价于对两个字符串进行排序后相等 * 也可以使用哈希表维护一个字符串存在的字符和出现的次数，再遍历另一个字符串对第一个出现的次数逐渐减少，若少于0则不相等 * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/7 11:04 */ public class 有效的字母异位词242 { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } Map<Character, Integer> map = new HashMap<>(); for (int i=0; i<s.length(); i++) { map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1); } for (int i=0; i<t.length(); i++) { map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) - 1); if (map.get(t.charAt(i)) < 0) { return false; } } return true; } }
二、赎金信
题目链接：383.赎金信
/** * <pre> * 想要让magazine中的单词可以组成ransomNote中的单词，那么magazine要涵盖ransomNote，字母出现的大于等于ransomNote * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/7 11:21 */ public class 赎金信383 { public boolean canConstruct(String ransomNote, String magazine) { if (magazine.length() < ransomNote.length()) { return false; } Map<Character, Integer> map = new HashMap<>(); for (int i=0; i<magazine.length(); i++) { map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) + 1); } for (int i=0; i<ransomNote.length(); i++) { Integer cnt = map.getOrDefault(ransomNote.charAt(i), 0); if (cnt == 0) { return false; } map.put(ransomNote.charAt(i), cnt - 1); } return true; } }
三、字母异位词分组
题目链接：49.字母异位词分组
/** * <pre> * 这道题主要提示我们哈希表的key不要被局限，之前时两个字符串进行比较，所以采用出现的每个字母作为键，出现次数作为值。但是对于本题，要比较的是多个字符串，那我们需要把握字母异位词的特征，属于字母异位词的多个字符串排序后相同或对他们使用字母-次数的表示方式相同，所以我们可以对字符串排序后存入map(n*k*logk)，也可以对每个字符串求出各个字符数量作为键存入(n*(k+26)) * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/7 11:29 */ public class 字母异位词分组49 { // 无脑解法，化成两个字符串比较问题两两比较，因为要在两重循环里面比较 public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> res = new ArrayList<>(); Map<Character, Integer> map = new HashMap<>(); for (int i=0; i< strs.length; i++) { if (strs[i] == null) { continue; } List<String> list = new ArrayList<>(); list.add(strs[i]); for (int j=i+1; j<strs.length; j++) { if (strs[j] != null && strs[i].length() == strs[j].length()) { map.clear(); for (int k=0; k<strs[i].length(); k++) { map.put(strs[i].charAt(k), map.getOrDefault(strs[i].charAt(k), 0) + 1); } boolean flag = true; for (int k=0; k<strs[j].length(); k++) { if (map.getOrDefault(strs[j].charAt(k), 0) == 0) { flag = false; break; } map.put(strs[j].charAt(k), map.getOrDefault(strs[j].charAt(k), 0) - 1); } if (flag) { list.add(strs[j]); strs[j] = null; } } } res.add(list); } return res; } // 排序 public List<List<String>> groupAnagrams2(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { char[] chars = str.toCharArray(); Arrays.sort(chars); String tmp = new String(chars); List<String> list = map.getOrDefault(tmp, new ArrayList<>()); list.add(str); map.put(tmp, list); } return new ArrayList<>(map.values()); } // 计数 public List<List<String>> groupAnagrams3(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { int[] letters = new int[26]; for (int i=0; i<str.length(); i++) { letters[str.charAt(i)-'a']++; } StringBuilder sb = new StringBuilder(); for (int i=0; i<26; i++) { if (letters[i] != 0) { sb.append('a' + i); sb.append(letters[i]); } } String key = sb.toString(); List<String> list = map.getOrDefault(key, new ArrayList<>()); list.add(str); map.put(key, list); } return new ArrayList<>(map.values()); } }
四、找到字符串中所有字母异位词
题目链接：438.找到字符串中所有字母异位词
/** * <pre> * 维护一个长度为p.length()的滑动窗口和一个数组记录窗口内给个字母出现的次数，每次移动时窗口左临界的字母移去，加上右临界的字母 * 每次移动后判断窗口数组和p产生的数组是否相同 * 由于比较数组需要O(n)的时间复杂度，可以使用一个dis变量记录当前两个数组不同字符的数量，dis为0时可选，时间复杂度优化为O(1) * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/7 13:20 */ public class 找到字符串中所有字母异位词438 { public List<Integer> findAnagrams(String s, String p) { ArrayList<Integer> list = new ArrayList<>(); int lens = s.length(); int lenp = p.length(); if (lens < lenp) { return list; } char[] sc = new char[26]; char[] pc = new char[26]; for (int i=0; i<lenp; i++) { sc[s.charAt(i)-'a']++; pc[p.charAt(i)-'a']++; } for (int i=0; i<lens-lenp; i++) { if (Arrays.equals(sc, pc)) { list.add(i); } sc[s.charAt(i)-'a']--; sc[s.charAt(i+lenp)-'a']++; } if(Arrays.equals(sc, pc)) { list.add(lens-lenp); } return list; } // 优化 public static List<Integer> findAnagrams2(String s, String p) { ArrayList<Integer> list = new ArrayList<>(); int lens = s.length(); int lenp = p.length(); if (lens < lenp) { return list; } int dis = 0; int[] count = new int[26]; // 维护的是两个字符串对于每个字母的数量差，正数表示p字符串多了几个，负数表示p字符串少了几个 for (int i=0; i<lenp; i++) { count[s.charAt(i)-'a']++; count[p.charAt(i)-'a']--; } for (int i=0; i<26; i++) { if (count[i] != 0) { dis++; } } for (int i=0; i<lens-lenp; i++) { if (dis == 0) { list.add(i); } int i1 = s.charAt(i) - 'a'; if (count[i1] == 0) { // 某个字母数量差等于0时减去移除该元素会导致多一个不满足要求 dis++; } else if (count[i1] == 1) { dis--; } count[i1]--; int i2 = s.charAt(i + lenp) - 'a'; if (count[i2] == -1) { // 某个字母数量差等于0时减去移除该元素会导致多一个不满足要求 dis--; } else if (count[i2] == 0) { dis++; } count[i2]++; } if (dis==0) { list.add(lens-lenp); } return list; } }
