刷穿剑指offer-Day09-字符串II 使用哈希表解决字符串
昨日回顾
从昨天开始，我们进入了第三章字符串的学习。然而所为的字符串专题，在讲解后，大家应该了解到字符串的题目，其实都是将字符串转化为其他数据类型后，再进行解题的过程。例如字符串转化为数组、栈、哈希表、队列等等。
昨天在文末，将剑指offer的015题作为课后作业留给大家下来练习。不知道有多少人自觉完成了呢？我猜没几个....
那么今天开篇，想讲解一下昨天的作业吧。
剑指OfferII015.字符串中的所有变位词
https://leetcode-cn.com/problems/VabMRr/solution/shua-chuan-jian-zhi-offer-day09-zi-fu-ch-f3mv/
难度：中等
题目：
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
提示:
- 1 <= s.length, p.length <= 3 * 10 ^ 4
- s 和 p 仅包含小写字母
示例：
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。
分析
昨天的文章中，我们学习使用长度为26的数组，来建立字符串数量与数组下标对应关系的操作。
通过对应关系，判断数组相等的方式，来实现字母异位词的操作。如果忘记了可以复习下昨天的解题
那么今天的这道题，相比于14题有什么变化么？答案是几乎没有...
昨天我们在循环过程中判断如果找到异位词立即返回，今天的题目，我们只需要在遇到异位词时记录此时的起始index，保存在数组。
然后返回数组即可，就这么点差别，看我们ctrl c v 14题的解题，快速解题。
解题：
Python：
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
arr1, arr2, lg, ret = [0] * 26, [0] * 26, len(p), []
if lg > len(s):
return []
for i in range(lg):
arr1[ord(p[i]) - ord('a')] += 1
arr2[ord(s[i]) - ord('a')] += 1
if arr1 == arr2:
ret.append(0)
for i in range(lg,len(s)):
arr2[ord(s[i]) - ord('a')] += 1
arr2[ord(s[i - lg]) - ord('a')] -= 1
if arr1 == arr2:
ret.append(i - lg + 1)
return ret
Java:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] arr1 = new int[26];
int[] arr2 = new int[26];
List<Integer> list = new ArrayList<Integer>();
if (p.length() > s.length()) {
return list;
}
for (int i = 0; i < p.length(); i++) {
arr1[p.charAt(i) - 'a']++;
arr2[s.charAt(i) - 'a']++;
}
if (Arrays.equals(arr1, arr2)) {
list.add(0);
}
for (int i = p.length(); i < s.length(); i++) {
arr2[s.charAt(i - p.length()) - 'a']--;
arr2[s.charAt(i) - 'a']++;
if (Arrays.equals(arr1, arr2)) {
list.add(i - p.length() + 1);
}
}
return list;
}
}
使用哈希表解字符串
昨天文章讲解和作业的两道题目，都是使用数组来解决字符串的题目，相信这个套路大家已经掌握了。
那么什么时候会使用到哈希表来解决字符串的问题呢？今天让我们来看一道这样的题目吧。
剑指offerII016.不含重复字符串的最长子字符串
https://leetcode-cn.com/problems/wtcaE1/solution/shua-chuan-jian-zhi-offer-day09-zi-fu-ch-tb4t/
难度：中等
题目：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
提示：
- 0 <= s.length <= 5 * 10 ^ 4
- s 由英文字母、数字、符号和空格组成
示例：
示例1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
分析：
这道题同样是通过滑动窗口来解题，只不过这次的边界获取要通过哈希表来实现。
- 首先我们创建一个哈希表calc，并且初始化左边界left = 0，默认返回值ret = 0
- 下来我们从0开始遍历字符串
- 每当遍历到字符串中的一个字符时，首先需要判断该字符是否在哈希表calc中
- 如果该字符串没有在哈希表中，表示该字符不重复，无需移动左边界，将该字符串及对应下标加入哈希表中
- 如果该字符存在哈希表中，表示找到了重复的元素，此时我们需要移动左边界left
- 若left小于哈希表中该字符对应的index下标，则移动至index + 1（因为index已经重复了，需要跳过）
- 若left大于哈希表中该字符对应的index下标，表示重复的内容在左边界以外，忽略即可
- 将当前字符串对应的下标更新哈希表中该字符串对应的下标
- 每次更新左边界后，比较当前滑窗长度与返回值大小并更新返回值
- 最终返回ret即可。
解题：
Python:
class Solution:
def lengthOfLongestSubstring(self, s):
calc = {}
left = 0
ret = 0
for i, j in enumerate(s):
if j in calc:
# 如果重复的数字出现在l之前忽略，否则了跳到该值的下一个位置
left = max(left, calc[j] + 1)
calc[j] = i
ret = max(ret, i - left + 1)
return ret
Java:
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> calc = new HashMap<>();
int left = 0;
int ret = 0;
for (int i = 0; i < s.length(); i++) {
if (calc.get(s.charAt(i)) != null) {
left = Math.max(left, calc.get(s.charAt(i)) + 1);
}
calc.put(s.charAt(i), i);
ret = Math.max(ret, i - left + 1);
}
return ret;
}
}
关于字符串的哈希表解题方式就讨论到这里，如果学有余力的朋友，可以看看017.含有所有字符的最短字符串，这是一道困难题，如果初学的朋友可以先放放，等完整学过哈希表这章节后再来做这道题会比较轻松写。
今天的文章就到这里，还是那句老话，编程是敲出来的，不是看出来的。看过文章一定要实操一遍，切记这样才能学好！
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
