算法七 哈希表与字符串（Java实现）
任意元素的映射
利用哈希函数，将关键字值(key)(大整数、字符串、浮点数等)转换为整数再对表长取余，从而关键字值被转换为哈希表的表长范围内的整数。
拉链法解决冲突，构造哈希表
将所有哈希函数结果相同的结点连接在同一个单链表中。若选定的哈希表长度为m，则可将哈希表定义为一个长度为m的指针数组t[0..m-1]， 指针数组中的每个指针指向哈希函数结果相同的单链表。
插入value:将元素value插入哈希表，若元素value的哈希函数值为hash_key,将value对应的节点以头插法的方式插入到以t[hash key]为头指针的单链表中。
查找value:若元素value的哈希函数值为hash_key,遍历以t[hash_ key]为头指针的单链表，查找链表各个节点的值域是否为value。
1、LeetCode409最长回文串
思路：1.利用字符哈希方法，统计字符串中所有的字符数量;
2.设置最长回文串偶数字符长度为max_ length = 0;
3.设置是否是否有中心点标记flag=0;
4.遍历每一个字符，字符数为count, 若count为偶数,max_ length += count;若count为奇数,max_ length += count-l, flag= 1;
5.最终最长回文子串长度: max_ length + flag。
class Solution { public int longestPalindrome(String s) { int[] char_map = new int[128];//字符哈希 int max_length = 0;//回文串偶数部分的最大长度 int flag = 0;//是否有中心点 for(int i=0;i<s.length();i++){ char c = s.charAt(i); char_map[c]++;//利用整数的数组下标实现字符哈希，统计字符个数 } for(int i=0;i<128;i++){ if(char_map[i]%2 == 0){//如果某字符为偶数个，则均可以使用在回文串里 max_length += char_map[i]; }else{ max_length += char_map[i]-1;//如果某字符为奇数个，则丢弃一个，其余的使用在回文串里 flag = 1;//此时标记回文串可以有中心点 } } return max_length + flag;//最终结果是偶数部分的最大长度+中心点字符 } } 复制代码2、LeetCode290单词规律
思路：1.设置单词(字符串)到pattern字符的映射(哈布);使用数组used[128]记录pattern字符是否使用。
2.遍历str，按照空格拆分单词，同时对应的向前移动指向pattern字符的指针，每拆分出一个单词，判断:
如果该单词从未出现在哈希表中:如果当前的pattern字符已被使用，则返回false;将单词与当前指向的attern字符做映射;标记当前指向的pattern字符已使用，否则:如果当前单词在哈希表中的映射字符不是当前指向的pattern字符，则返回false。
3.若单词个数与pattern字符个数不匹配，返回false。
LeetCode评论代码
class Solution { public boolean wordPattern(String pattern, String s) { String[] strings = s.split(" "); if (pattern.length() != strings.length) { return false; } HashMap<Object, Integer> hashMap = new HashMap<>(); //如果出现位置不匹配，或者一个已经出现而另一个没有出现过，则匹配失败。使用Objects.equals方法可以避免对null值进行判断 for (int i = 0; i < pattern.length(); i++) { if(!Objects.equals(hashMap.put(pattern.charAt(i), i), hashMap.put(strings[i], i))){ return false; } } return true; } } 复制代码3、LeetCode49字母异位词分组
思路：设置字符串到字符串向量的哈希表anagram,遍历字符串向量strs中的单词strs[i]:
1)设置临时变量str = strs[i]，对str进行排序。
2)若sr未出现在anagram中，设置str到一个空字符串向量的映射。
3)将strs[i]添加至字符串向量anagram[str]中。
遍历哈希表anagram，将全部key对应的value push至最终结果中。
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (int i = 0; i < strs.length; i++) { char[] chars = strs[i].toCharArray(); //对字符串内部进行字符排序 Arrays.sort(chars); String key = String.valueOf(chars); //根据key放入不同的组 if (!map.containsKey(key)) { //若无法在哈希表中找到key，设置一个空的字符串 List<String> list = new ArrayList<>(); list.add(strs[i]); map.put(key, list); } else { //在对应的字符串中push结果 map.get(key).add(strs[i]); } } return new ArrayList<>(map.values()); } } 复制代码4、LeetCode3无重复字符的最长子串
思路：1.设置一个记录字符数量的字符哈希,char_map;
2.设置一个记录当前满足条件的最长子串变量word;
3.设置两个指针(记作指针i与指针begin)指向字符串第一个字符;
4.设置最长满足条件的子串的长度result;
5.i指针向后逐个扫描字符串中的字符，在这个过程中，使用char_ map记录字符数量。如果word中没出现过该字符:对word尾部添加字符并检查result是否需要更新;否则:begin指针向前移动，更新char_map中的字符数量，直到字符s[i]的数量为1;更新word,将word赋值为begin与i之间的子串。
在整个过程中，使用begin与i维护一个窗口,该窗口中的子串满足题目条件(无重复的字符)，窗口线性向前滑动，整体时间复杂度为O(n)。
LeetCode评论代码
class Solution { public int lengthOfLongestSubstring(String s) { int result=0; int start=0,end=0;//代表当前窗口的开始和结束位置 Set<Character> set=new HashSet<Character>(); //当窗口中出现重复的字符时，start++,没有重复时，end++,每次更新长度的最大值 while(start<s.length() && end<s.length()){ if(set.contains(s.charAt(end))){ set.remove(s.charAt(start)); start++; } else{ set.add(s.charAt(end)); end++; result=Math.max(result, end-start); } } return result; } } 复制代码5、LeetCode189重复的DNA序列
思路：枚举DNA字符串的中所有长度为10的子串，将其插入到哈希Map中，并记录子串数量；遍历哈希map,将所有出现超过1次的子串存储到结果中。算法复杂度O(n)。
LeetCode官方题解
class Solution { public List<String> findRepeatedDnaSequences(String s) { int L = 10, n = s.length(); HashSet<String> seen = new HashSet(), output = new HashSet(); for (int start = 0; start < n - L + 1; ++start) { String tmp = s.substring(start, start + L); if (seen.contains(tmp)) output.add(tmp); seen.add(tmp); } return new ArrayList<String>(output); } } 复制代码6、LeetCode76最小覆盖子串
思路：1.设置两个字符哈希数组，map_ s与map_t, map_s代表当前处理的窗口区间中的字符数量,map_ t代表子串T的字符数量。
2.设置两个指针(记作指针i与指针begin)指向字符串第一个字符;
3.i指针向后逐个扫描字符串中的字符，在这个过程中，循环检查begin指针是否可以向前移动;
如果当前begin指向的字符T中没出现，直接前移begin; 如果begin指向的字符T中出现了， 但是当前区间窗口中的该字符数量足够，向前移动begin,并更新map_ s;否则不能移动begin,跳出检查。
4.指针每向前扫描一个字符， 即检查一下是否可以更新最终结果(找到最小的包含T中各个字符的窗口)。在整个过程中，使用begin与i维护一个窗口，该窗口中的子串满足题目条件(包含T中所有字符)，窗口线性向前滑动，整体时间复杂度为O(n)。
LeetCode评论代码
class Solution { public static String minWindow(String s, String t) { int left = 0,right = 0; int count = t.length(); int res_left = 0; int res_right = -1; int substringLen = Integer.MAX_VALUE; int[] map = new int[128]; for (int i = 0; i < t.length(); i++) { map[t.charAt(i)]++; } while (right < s.length()) { map[s.charAt(right)]--; if (map[s.charAt(right)] >= 0) { count--; } while (count == 0) { int tempLen = right - left + 1; if (substringLen > tempLen) { res_left = left; res_right = right; substringLen = tempLen; } char departingCharacter = s.charAt(left); map[departingCharacter]++; if (map[departingCharacter] > 0) { count++; } left++; } right++; } return s.substring(res_left, res_right + 1); } }
作者：zust_Isabella
链接：https://juejin.cn/post/7003596346934427655