【LeetCode】剑指 Offer Ⅱ 第3章：字符串（7道题） -- Java Version

题库链接：https://leetcode.cn/problem-list/e8X3pBZi/

题目	解决方案
剑指 Offer II 014. 字符串中的变位词	双指针 + 数组模拟哈希表 ⭐
剑指 Offer II 015. 找到字符串中所有字母异位词	双指针 + 数组模拟哈希表 ⭐
剑指 Offer II 016. 不含重复字符的最长子字符串	双指针 + 数组模拟哈希表 ⭐
剑指 Offer II 017. 最小覆盖子串	双指针 + 哈希表 ⭐
剑指 Offer II 018. 有效的回文	双指针（前后）⭐
剑指 Offer II 019. 最多删除一个字符得到回文	双指针（前后）⭐
剑指 Offer II 020. 回文子字符串的个数	双指针（从回文中心出发）⭐

本章的题目主要分为两种类型：变位词 和 回文；
……
如果将 字符串 看成一个由字符组成的数组，那么也可以用两个指针来定位一个子字符串，其中一个指针指向字符串的第1个字符，另一个指针指向字符串的最后一个字符，两个指针之间所包含的就是一个子字符串。
……
一般来说，就双指针的字符串问题而言，这种类型的面试题基本上都与 统计字母出现的次数 有关，我们常用 哈希表 来存储每个元素出现的次数。

1. 剑指 Offer II 014. 字符串中的变位词 – P31

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

1.1 滑动窗口 – O(m+n)

时间复杂度 $O(m+n)$，空间复杂度 $O(n)$

窗口定长为 n，每次向前移动一格.

class Solution {// 1. 滑动窗口public boolean checkInclusion(String s1, String s2) {int n = s1.length(), m = s2.length();if (n > m) return false;  // 如果 n > m，则 s2 中必不存在 s1 的变位词int[] cnt1 = new int[26];  // 26个英文字母int[] cnt2 = new int[26];for (int i = 0; i < n; i++) {++cnt1[s1.charAt(i) - 'a'];++cnt2[s2.charAt(i) - 'a'];}if (Arrays.equals(cnt1, cnt2)) return true; for (int i = n; i < m; i++) {++cnt2[s2.charAt(i) - 'a'];--cnt2[s2.charAt(i-n) - 'a'];if (Arrays.equals(cnt1, cnt2)) return true;}return false;}
}

1.2 双指针 + 数组模拟哈希表 – O(m+n)（⭐）

时间复杂度 $O(m+n)$，空间复杂度 $O(n)$

class Solution {// 2. 双指针 + 数组模拟哈希表public boolean checkInclusion(String s1, String s2) {int n = s1.length(), m = s2.length();if (n > m) {return false;}int[] cnt = new int[26];for (int i = 0; i < n; i++) --cnt[s1.charAt(i) - 'a'];  // 让 s1 全为负数for (int l = 0, r = 0; r < m; r++) {  // 双指针遍历 s2，从 s2 中找出 s1 的变式int t = s2.charAt(r) - 'a';cnt[t]++;while (cnt[t] > 0) --cnt[s2.charAt(l++) - 'a'];if (r - l + 1 == n) return true;  // 说明此时 cnt 数组之和全为 0}return false;}
}

2. 剑指 Offer II 015. 找到字符串中所有字母异位词 – P35

给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
……
此题也可使用1题中 滑动窗口 的解法，但是滑动窗口 + 两个 cnt[] 的方法要比双指针的慢一些，为避免冗余，此处省略.

2.1 双指针 + 数组模拟哈希表 – O(m+n)（⭐）

时间复杂度 $O(m+n)$，空间复杂度 $O(n)$

class Solution {// 双指针public List<Integer> findAnagrams(String s, String p) {int n = s.length(), m = p.length();List<Integer> list = new LinkedList<>();int[] cnt = new int[26];  // 26个小写英文字母for (int i = 0; i < m; i++) --cnt[p.charAt(i) - 'a'];  // 初始化 p 串, 使cnt--for (int l = 0, r = 0; r < n; r++) {  // 双指针移动 s 串int t = s.charAt(r) - 'a';cnt[t]++;while (cnt[t] > 0) --cnt[s.charAt(l++) - 'a'];if (r - l +  1 == m) list.add(l);  // 在 s 中找到 p 的变位词，记录起始索引} return list;}
}

3. 剑指 Offer II 016. 不含重复字符的最长子字符串 – P36

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

3.1 双指针 + 数组模拟哈希表 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

class Solution {// 1. 双指针 + 数组模拟哈希表public int lengthOfLongestSubstring(String s) {int n = s.length();if (n == 0) return 0;int res = 0;int[] ascii = new int[256];  // 与前两题不同的是，这次不局限于小写英文字母了for (int l = 0, r = 0; r < n; r++) {int t = s.charAt(r);ascii[t]++;while (ascii[t] > 1) --ascii[s.charAt(l++)];  // ascii[i] > 0, 说明出现了重复字符，开始移动 l res = Math.max(res, r - l + 1);  // 记录不重复子字符串的长度}return res;}
}

3.2 HashSet – O(n)

时间复杂度 $O(n)$，空间复杂度 $O(n)$

class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合，记录每个字符是否出现过Set<Character> set = new HashSet<Character>();int n = s.length();// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动int r = -1, ans = 0;for (int l = 0; l < n; l++) {if (l != 0) {// 左指针向右移动一格，移除一个字符set.remove(s.charAt(l - 1));}while (r + 1 < n && !set.contains(s.charAt(r + 1))) {// 不断地移动右指针set.add(s.charAt(r + 1));++r;}// 第 l 到 r 个字符是一个极长的无重复字符子串ans = Math.max(ans, r - l + 1);}return ans;}
}

PS：补充知识1 - 【HashSet】

💡 HashSet集合(元素无序且唯一)，其底层是哈希表，特点：

• 无序；
• 不可重复；
• 不能排序；

……
元素的唯一性是靠元素重写 hashCode() 和 equals() 方法来保证的,如果不重写则无法保证唯一性.(Integer以及String类等都已经重写了这两个方法,一定要注意自己定义的类需要重写才能确保唯一性!)
……
更多内容可参考：
[1] 单列集合Set的实现类HashSet - 陪雨岁岁年年的博客
[2] Java-单列集合（Collection,List,Set集合的详细介绍）- 壹万捌先生的博客

4. 剑指 Offer II 017. 最小覆盖子串 – P39

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 “” 。

4.1 双指针 + 哈希表 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

class Solution {public String minWindow(String s, String t) {int n = s.length(), m = t.length();Map<Character,Integer> tmap = new HashMap<>();for (int i = 0; i < m; i++) tmap.put(t.charAt(i), tmap.getOrDefault(t.charAt(i),0)+1);int count = 0;Map<Character,Integer> smap = new HashMap<>();String res = "";for (int l = 0, r = 0; r < n; r++) {char rch = s.charAt(r);smap.put(rch, smap.getOrDefault(rch,0)+1);if (smap.get(rch) <= tmap.getOrDefault(rch,0)) {  // 排除重复冗余字符count++;}while (smap.getOrDefault(s.charAt(l),0) > tmap.getOrDefault(s.charAt(l),0) && l < r) {  // 当子字符串超过所需匹配字符时，移动lsmap.put(s.charAt(l), smap.getOrDefault(s.charAt(l),0)-1);l++;}if (count == m) {if (res.isEmpty() || (r - l + 1) < res.length()){  // 比较找出最小字符串res = s.substring(l, r + 1);}}}return res;}
}

4.2 双指针 + 数组模拟哈希表 – O(n)

时间复杂度 $O(n)$，空间复杂度 $O(n)$

相比于4.1要更快，但是相对也要更难记忆.

class Solution {public String minWindow(String s, String t) {int[] map = new int[256];for(char c: t.toCharArray()){  // 初始化 t 字符串map[c]++;}int minLen = Integer.MAX_VALUE, minStart = 0;  // 设定最短字符串的长度和起始位置int m = t.length(), n = s.length();char[] sc = s.toCharArray();for (int l = 0, r = 0; r < n; r++){int rch = sc[r];map[rch]--;if(map[rch] >= 0){  // 减小与 t 的字符差距m--; }if(m == 0){  // 成功在 s 中匹配到包含 t 的子字符串int lch = sc[l];while(map[lch] < 0){  // 开始尝试缩小窗口范围map[lch]++;l++;lch = sc[l];  }int len = r - l + 1;if(len < minLen){  // 找出最小子字符串minLen = len;minStart = l;}map[lch]++;l++;m++;}}return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);}
}

5. 剑指 Offer II 018. 有效的回文 – P42

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

5.1 双指针（前后）-- O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

class Solution {// 双指针：需要注意的是，有效字符包括：英文字母、数字和空格public boolean isPalindrome(String s) {int n = s.length();char[] sch = s.toLowerCase().toCharArray();for (int l = 0, r = n-1; l < r;) {if (!Character.isLetterOrDigit(sch[l])) l++;  // 判断是否为英文字母或数字else if (!Character.isLetterOrDigit(sch[r])) r--;else {if (sch[l] != sch[r]) return false;  // 前后指针不相同，说明非回文l++;r--;}}return true;}
}

PS：补充知识1 - 【Character包装类 – 8种方法】

判断一个字符是否是数字、英文、其他字符.

// 1. 判断该字符是否是字母，是返回true，否返回false
Character.isLetter(char ch)
// 2. 判断一个字符是否是数字字符，是返回true，否返回false
Character.isDigit(char ch)	
// 3. 判断该字符是字母还是数字，如果字符是字母或数字返回true; 否则false。
Character.isLetterOrDigit(char ch)
// 4. 判断指定字符是否为空白字符，空白符包含：空格、tab 键、换行符
Character.isWhitespace(char ch) 
// 5. 判断该字符是否是小写字母,是返回true，否返回false
Character.isLowerCase(char ch)
// 6. 判断该字符是否是大写字母,是返回true，否返回false
Character.isUpperCase(char ch)
// 7. 将小写字符转换为大写
Character.toUpperCase('A')
// 8. 将大写字符转换为小写
Character.toUpperCase('a')
// 9. 用于返回一个表示指定 char 值的 String 对象。结果是长度为 1 的字符串，仅由指定的 char 组成。
Character.toString('a')

6. 剑指 Offer II 019. 最多删除一个字符得到回文 – P43

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

6.1 双指针（前后）-- O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

class Solution {public boolean validPalindrome(String s) {int n = s.length();char[] sch = s.toCharArray();int l = 0, r = n-1;for (; l < r; l++, r--) {if (sch[l] != sch[r]) break;  // 找到第一次不同之处}return isPalindrome(l+1,r,sch) || isPalindrome(l,r-1,sch);  // 删左或删右}public boolean isPalindrome(int l, int r, char[] sch) {  // 再次利用双指针进行回文判断while (l < r) {if (sch[l] != sch[r]) return false;l++;r--;}return true;}
}

6.2 双指针（前后）+StringBuilder – O(n)

时间复杂度 $O(n)$，空间复杂度 $O(1)$

速度并不会提升，且书写代码量似乎也不会渐少，总之不太推荐这种写法。

class Solution {public boolean validPalindrome(String s) {int n = s.length();int l = 0, r = n - 1;while (l < r) {if (s.charAt(l) != s.charAt(r)) break;l++;r--;}if (r <= l) return true;String ls = s.substring(l+1, r+1);  // substring(), 左闭右开StringBuilder stringBuilder = new StringBuilder(ls);String rs = s.substring(l, r);StringBuilder stringBuilder2 = new StringBuilder(rs);return ls.equals(stringBuilder.reverse().toString()) || rs.equals(stringBuilder2.reverse().toString());}
}

PS：补充知识1 - 【substring() 方法】

substring() 方法返回字符串的子字符串，左闭右开区间 [beginIndex, endIndex)。

public class RunoobTest {public static void main(String args[]) {String Str = new String("This is text");System.out.print("返回值 :" );System.out.println(Str.substring(4) );  // 返回值 : is textSystem.out.print("返回值 :" );System.out.println(Str.substring(4, 10) );  // 返回值 : is te}
}

7. 剑指 Offer II 020. 回文子字符串的个数 – P44

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

7.1 双指针（从回文中心出发）-- O(n²)（⭐）

时间复杂度 $O(n^2)$，空间复杂度 $O(1)$

class Solution {// 双指针：从回文中心出发public int countSubstrings(String s) {int n = s.length();if (n <= 1) return n;int count = 0;char[] sch = s.toCharArray();for (int i = 0; i < n; i++) {count += countPalindrome(sch, i, i);  // 奇数长度：一个对称中心count += countPalindrome(sch, i, i+1);  // 偶数长度：两个对称中心}return count;}public int countPalindrome(char[] sch, int l, int r) {int count = 0;while (l >= 0 && r < sch.length && sch[l] == sch[r]) {count++;l--;r++;}return count;}
}