双指针[滑动窗口]+哈希表
变位词
- 定义
变位词是指组成各个单词的字母及每个字母出现的次数完全相同，只是字母排列的顺序不同。如“pots”、“stop”和“tops”
- 特点
。长度相同
。字母集合相同，并且每个字母出现的次数相同
字符串中的排列【LC567】
2022/10/27
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
- 思路：s1的字符在s2中全部存在，并且连续（子串），返回true
。记录第一出现的字符的位置和最后一个出现的字符的位置，如果相减长度为s1的长度，那么证明是连续出现的子串
- 不对 字母可能多次出现 并且重复出现
。逐一判断字符串s2中长度为n的子字符串是不是字符串s1的变位词
- 实现
。使用哈希表存储s1中出现的字符及其次数
。使用双指针定位一个子字符串，其中一个指针left指向子字符串的第一个字符，另一个指针指向子字符串的最后一个字符
- 每当在子字符串中添加一个字符时，就把哈希表中对应位置的值减1
- 每当在子字符串中删除一个字符时，就把哈希表中对应位置的值加1
。如果子字符串对应的charToCount全为0，那么证明该子字符串为字符串s1的变位词，返回true
。代码
class Solution { public boolean checkInclusion(String s1, String s2) { if (s1.length() > s2.length()){ return false; } int len1 = s1.length(); int[] charToCount = new int[26]; for (int i = 0; i < len1; i++){ charToCount[s1.charAt(i)-'a']++; charToCount[s2.charAt(i)-'a']--; } if (areAllZeor(charToCount)){ return true; } for (int i = len1; i < s2.length(); i++){ charToCount[s2.charAt(i-len1)-'a']++;// 删除左指针对应的字符 charToCount[s2.charAt(i)-'a']--;// 添加右指针对应的字符 if (areAllZeor(charToCount)){ return true; } } return false; } public boolean areAllZeor(int[] charToCount){ for (int i = 0; i < charToCount.length; i++){ if (charToCount[i] != 0){ return false; } } return true; } }
。复杂度
- 时间复杂度：O(n+m)
- 空间复杂度：O(1)
字符串中所有的变位词【LC438】
2022/10/27
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
- 思路：逐一判断字符串s中长度为lenP的子字符串是不是字符串p的变位词，如果是则将起始索添加至结果集
- 实现
。使用哈希表存储p中出现的字符及其次数
。使用双指针定位一个子字符串，其中一个指针left指向子字符串的第一个字符，另一个指针指向子字符串的最后一个字符
- 每当在子字符串中添加一个字符时，就把哈希表中对应位置的值减1
- 每当在子字符串中删除一个字符时，就把哈希表中对应位置的值加1
。如果子字符串对应的charToCount全为0，那么证明该子字符串为字符串p的变位词，则将起始索添加至结果集
。最后返回结果集
- 代码
class Solution { public boolean checkInclusion(String s1, String s2) { if (s1.length() > s2.length()){ return false; } int len1 = s1.length(); int[] charToCount = new int[26]; for (int i = 0; i < len1; i++){ charToCount[s1.charAt(i)-'a']++; charToCount[s2.charAt(i)-'a']--; } if (areAllZeor(charToCount)){ return true; } for (int i = len1; i < s2.length(); i++){ charToCount[s2.charAt(i-len1)-'a']++;// 删除左指针对应的字符 charToCount[s2.charAt(i)-'a']--;// 添加右指针对应的字符 if (areAllZeor(charToCount)){ return true; } } return false; } public boolean areAllZeor(int[] charToCount){ for (int i = 0; i < charToCount.length; i++){ if (charToCount[i] != 0){ return false; } } return true; } }
。复杂度
- 时间复杂度：O(n+m)
- 空间复杂度：O(1)
不含重复字符的最长子字符串【LC3】
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
2022/10/27
哈希表+双指针
- 思路：使用双指针定位一个子字符串，使用哈希表判断子字符串是否存在重复元素，如果有重复元素，当出现重复字符，收缩左边界直到重复字符消失
- 实现
。使用哈希set存储目前存放的字符
。使用双指针定位一个子字符串，其中一个指针left指向子字符串的第一个字符，另一个指针指向子字符串的最后一个字符
- 每当当前字符不位于哈希表中时，向右移动right
- 每当当前字符位于哈希表中时，
- 判断是否需要更新res，此时子字符串的长度为right-left
- 然后向右移动left，找到重复的位置，并找到新的初始位置[每移动一次left，需要将对应的字符在哈希表中删除]
。最后返回结果
- 代码 hashset
class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> words = new HashSet<>(); int res = 0; int left = 0; int right = 0; while ( left <= right && right < s.length()){ if (!words.contains(s.charAt(right))){ words.add(s.charAt(right)); }else{ res = Math.max(res,right - left); while (left < s.length() && s.charAt(left) != s.charAt(right)){ words.remove(s.charAt(left)); left++; } left++; } right++; } res = Math.max(res,right - left); return res; } }
。复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1),hashset最大的容量为ASCII码的多少，为256
- 代码 boolean数组
class Solution { public int lengthOfLongestSubstring(String s) { boolean[] words = new boolean[256]; int res = 0; int left = 0; int right = 0; while ( left <= right && right < s.length()){ if (!words[s.charAt(right)]){ words[s.charAt(right)] = true; }else{ res = Math.max(res,right - left); while (left < s.length() && s.charAt(left) != s.charAt(right)){ words[s.charAt(left)] = false; left++; } left++; } right++; } res = Math.max(res,right - left); return res; } }
含有所有字符的最短字符串/最小覆盖子串【LC76】
给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
如果 s 中存在多个符合条件的子字符串，返回任意一个。
注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
[可以包括其他字符的最短’变位词’]
2022/10/29
- 思路：使用双指针定位s的子字符串，使用哈希表记录出现的字母及次数
。当该子字符串包含t的所有字符时，判断是否是最短子字符串，是则记录左右边界
。如果左边界出现重复字符并且不是所需要的字符，那么收缩左边界
- 实现：
。使用哈希表存储t中出现的字符及其次数
。使用双指针定位一个子字符串，其中一个指针left指向子字符串的第一个字符，另一个指针right指向子字符串的最后一个字符
- 每当在子字符串中添加一个字符时，就把哈希表中对应位置的值减1
- 每当在子字符串中删除一个字符时，就把哈希表中对应位置的值加1
。如果子字符串对应的charToCounts全为0，那么证明该子字符串包含t的所有字符，判断是否是最短子字符串，是则记录左右边界
。最后返回判断是否存在子字符串，是则返回s.sbstring(left,right)，否则返回空字符串
- 代码
class Solution { public String minWindow(String s, String t) { if (s.length() < t.length()){ return ""; } int[] charToCounts = new int['z'-'A'+1]; int left = 0; int right = 0; int minLeft = 0;// 左闭右闭 int minRight = Integer.MAX_VALUE; for (; right < t.length(); right++){ charToCounts[t.charAt(right)-'A']++; charToCounts[s.charAt(right)-'A']--; } if (isContainsAll(charToCounts)){ minRight = right - 1; } while (right < s.length()){ charToCounts[s.charAt(right)-'A']--; // 左边界有重复字符或者不是所需字符 收缩左边界 while (left <= right && charToCounts[s.charAt(left)-'A'] < 0){ charToCounts[s.charAt(left)-'A']++; left++; } if (isContainsAll(charToCounts)){// 包含全部字符 if (right - left < minRight - minLeft){ minRight = right; minLeft = left; } } right++; } return minRight == Integer.MAX_VALUE ? "" : s.substring(minLeft,minRight+1); } public boolean isContainsAll(int[] charToCounts){ for(int i = 0; i < charToCounts.length; i++){ if (charToCounts[i] > 0){ return false; } } return true; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(C),charToCounts的容量为’z’-‘A’+1
字符串中不同整数的数目【LC1805】
You are given a string word that consists of digits and lowercase English letters.
You will replace every non-digit character with a space. For example, "a123bc34d8ef34" will become " 123 34 8 34". Notice that you are left with some integers that are separated by at least one space: "123", "34", "8", and "34".
Return the number of different integers after performing the replacement operations on word.
Two integers are considered different if their decimal representations without any leading zeros are different.
2022/12/6
- 思路：使用双指针定位字符串中整数的起始位置和结束位置，去除前导0后，将该整数放入哈希表中，最后返回哈希表的大小即可。
。如果左指针为字母，那么右移左指针，左指针为整数的起始位置
。如果右指针为数字，那么右移右指针，右指针为整数的结束位置+1
- 实现
class Solution { public int numDifferentIntegers(String word) { Set<String> set = new HashSet<>(); int len = word.length(); int l = 0; int r = 0; while (l < len && r < len){ // 找到左边界 while (l < len && word.charAt(l) >= 'a' && word.charAt(l) <= 'z'){ l++; } if (l == len){ break; } // 找到右边界 r = l; while ( r < len && word.charAt(r) >= '0' && word.charAt(r) <= '9') { r++; } // 去除前导0 while (l != r && word.charAt(l) == '0'){ l++; } String num = word.substring(l, r); set.add(num); l = r + 1; } return set.size(); } }
。复杂度
- 时间复杂度：O(n)
- 空间复杂度：$
