精选专栏链接 力扣 hot 100系列专栏MySQL技术笔记专栏Redis技术笔记专栏消息中间件专栏大模型专栏Python学习笔记专栏深度学习算法专栏欢迎订阅点赞关注每日精进1%与百万开发者共攀技术珠峰更多内容持续更新中~【LeetCode 热题 100】找到字符串中所有字母异位词题目描述提示信息 字母异位词是什么 解题思路一暴力枚举 解题思路二滑动窗口 数组计数题目描述给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:输入: scbaebabacd, pabc输出:[0,6]解释: 起始索引等于0的子串是cba, 它是abc的异位词。 起始索引等于6的子串是bac, 它是abc的异位词。示例 2:输入: sabab, pab输出:[0,1,2]解释: 起始索引等于0的子串是ab, 它是ab的异位词。 起始索引等于1的子串是ba, 它是ab的异位词。 起始索引等于2的子串是ab, 它是ab的异位词。提示信息1 s.length, p.length 3 *10 4 10^4104s 和 p 仅包含小写字母 字母异位词是什么字母异位词指的是两个字符串包含的字符完全相同每个字符出现次数一致仅顺序不同。例如 “abc” 和 “bca” 是异位词 “aab” 和 “aba” 也是异位词。 解题思路一暴力枚举既然要找 s 中长度为 p.length() 的子串最直观的做法是截取从 s 的第 0 位开始每次截取一段长度等于 p 的子串比较拿着这个子串去跟 p 比看是不是异位词移动起始位置 1重复上述步骤。暴力枚举法代码实现如下classSolution{publicListIntegerfindAnagrams(Strings,Stringp){ListIntegerresultnewArrayList();intsLens.length();intpLenp.length();// 将 p 转为字符数组并排序作为比较的标准char[]pCharsp.toCharArray();Arrays.sort(pChars);StringsortedPnewString(pChars);// 遍历 s 中所有可能的子串起点for(inti0;isLen-pLen;i){// 截取长度为 pLen 的子串注意substring字母都是小写Stringsubs.substring(i,ipLen);// 将子串也排序后与 p 比较char[]subCharssub.toCharArray();Arrays.sort(subChars);StringsortedSubnewString(subChars);if(sortedP.equals(sortedSub)){result.add(i);}}returnresult;}}提交代码运行结果如下可以看出暴力枚举法效率实际上并不高。暴力枚举法的缺陷假设 s 的长度是 N p 的长度是 M 。我们要移动约 N 次。每次移动后都要重新排序。暴力枚举法的时间复杂度为 (⋅log) 。每次循环都要对子串进行排序暴力枚举法的空间复杂度为 () 用于存储排序后的字符数组。知识点补充在 Java 中Arrays.sort()对基本数据类型如char[]使用的是双轴快速排序其平均时间复杂度是O ( n log n ) O(n \log n)O(nlogn)。其中 n 是字符串p的长度。 解题思路二滑动窗口 数组计数我们需要在 s 中寻找长度恰好等于 p.length() 的子串。如果使用暴力枚举每次窗口向右移动一格我们都要重新统计整个新窗口的字符频率这会造成大量的重复计算。而滑动窗口的核心思想是 “增量更新”。当窗口向右滑动一格时实际上只发生了两件事左边界有一个字符离开了窗口右边界有一个新字符进入了窗口。因此我们只需要在旧的统计结果上把离开的字符计数减 1把进来的字符计数加 1就能在 O(1) 的时间内得到新窗口的状态。具体例子如下① 初始窗口[0,2]子串是cba。我们需要遍历这3个字符统计出频率{c:1, b:1, a:1};② 窗口右移一格[1,3]子串变成了bae ③ 注意观察新窗口bae和旧窗口cba中间重叠了ba ④ 此时我们只需把刚离开窗口的左边字符c的计数减1。把刚进入窗口的新字符e的计数加1 ⑤ 经过两步简单的加减法sCount 数组变成了{b:1, a:1, e:1}这正是新窗口bae的频率代码实现如下classSolution{publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length();intpLenp.length();// 1. 边界处理如果 s 比 p 还短不可能存在异位词直接返回空列表if(sLenpLen){returnnewArrayListInteger();}ListIntegerresultnewArrayListInteger();// 2. 初始化两个频率统计数组长度为 26 对应 26 个小写英文字母int[]sCountnewint[26];int[]pCountnewint[26];// 3. 构建初始窗口统计 p 的字母频率以及 s 中前 pLen 个字母频率for(inti0;ipLen;i){// s.charAt(i) - a可将字符映射为数组索引。a的ASCII 值为 97sCount[s.charAt(i)-a];pCount[p.charAt(i)-a];// 此时sCount 记录了 s 中第一个窗口内各字母出现的频率pCount 记录了目标字符串的字母频率}// 4. 检查 初始窗口 是否匹配if(Arrays.equals(sCount,pCount)){result.add(0);}// 5. 核心滑动过程窗口从索引 1 开始一直滑动到 s 的末尾for(inti0;isLen-pLen;i){// 【出】窗口左边界字符离开将 s[i] 的计数减 1--sCount[s.charAt(i)-a];// 【进】窗口右边界新字符进入将 s[i pLen] 的计数加 1sCount[s.charAt(ipLen)-a];// 6. 比较当前窗口与目标字符串 p 的频率是否一致if(Arrays.equals(sCount,pCount)){// 注意此时窗口的起始索引是 i 1result.add(i1);}}returnresult;}}提交代码运行结果如下滑动窗口法 复杂度分析时间复杂度O(N)其中 N 是字符串 s 的长度M 为字符串 p 的长度初始化两个数组和初始窗口需要 O(M) 滑动窗口过程需遍历 O(N−M) 次每次操作加减计数 比较 26 个元素都是 O(1) 总体来看时间复杂度与 s 的长度成线性关系。空间复杂度O(1)仅使用了两个固定大小为 26 的整型数组 sCount 和 pCount以及几个辅助变量不随输入数据的规模增长。
【LeetCode 热题 100】找到字符串中所有字母异位词
精选专栏链接 力扣 hot 100系列专栏MySQL技术笔记专栏Redis技术笔记专栏消息中间件专栏大模型专栏Python学习笔记专栏深度学习算法专栏欢迎订阅点赞关注每日精进1%与百万开发者共攀技术珠峰更多内容持续更新中~【LeetCode 热题 100】找到字符串中所有字母异位词题目描述提示信息 字母异位词是什么 解题思路一暴力枚举 解题思路二滑动窗口 数组计数题目描述给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:输入: scbaebabacd, pabc输出:[0,6]解释: 起始索引等于0的子串是cba, 它是abc的异位词。 起始索引等于6的子串是bac, 它是abc的异位词。示例 2:输入: sabab, pab输出:[0,1,2]解释: 起始索引等于0的子串是ab, 它是ab的异位词。 起始索引等于1的子串是ba, 它是ab的异位词。 起始索引等于2的子串是ab, 它是ab的异位词。提示信息1 s.length, p.length 3 *10 4 10^4104s 和 p 仅包含小写字母 字母异位词是什么字母异位词指的是两个字符串包含的字符完全相同每个字符出现次数一致仅顺序不同。例如 “abc” 和 “bca” 是异位词 “aab” 和 “aba” 也是异位词。 解题思路一暴力枚举既然要找 s 中长度为 p.length() 的子串最直观的做法是截取从 s 的第 0 位开始每次截取一段长度等于 p 的子串比较拿着这个子串去跟 p 比看是不是异位词移动起始位置 1重复上述步骤。暴力枚举法代码实现如下classSolution{publicListIntegerfindAnagrams(Strings,Stringp){ListIntegerresultnewArrayList();intsLens.length();intpLenp.length();// 将 p 转为字符数组并排序作为比较的标准char[]pCharsp.toCharArray();Arrays.sort(pChars);StringsortedPnewString(pChars);// 遍历 s 中所有可能的子串起点for(inti0;isLen-pLen;i){// 截取长度为 pLen 的子串注意substring字母都是小写Stringsubs.substring(i,ipLen);// 将子串也排序后与 p 比较char[]subCharssub.toCharArray();Arrays.sort(subChars);StringsortedSubnewString(subChars);if(sortedP.equals(sortedSub)){result.add(i);}}returnresult;}}提交代码运行结果如下可以看出暴力枚举法效率实际上并不高。暴力枚举法的缺陷假设 s 的长度是 N p 的长度是 M 。我们要移动约 N 次。每次移动后都要重新排序。暴力枚举法的时间复杂度为 (⋅log) 。每次循环都要对子串进行排序暴力枚举法的空间复杂度为 () 用于存储排序后的字符数组。知识点补充在 Java 中Arrays.sort()对基本数据类型如char[]使用的是双轴快速排序其平均时间复杂度是O ( n log n ) O(n \log n)O(nlogn)。其中 n 是字符串p的长度。 解题思路二滑动窗口 数组计数我们需要在 s 中寻找长度恰好等于 p.length() 的子串。如果使用暴力枚举每次窗口向右移动一格我们都要重新统计整个新窗口的字符频率这会造成大量的重复计算。而滑动窗口的核心思想是 “增量更新”。当窗口向右滑动一格时实际上只发生了两件事左边界有一个字符离开了窗口右边界有一个新字符进入了窗口。因此我们只需要在旧的统计结果上把离开的字符计数减 1把进来的字符计数加 1就能在 O(1) 的时间内得到新窗口的状态。具体例子如下① 初始窗口[0,2]子串是cba。我们需要遍历这3个字符统计出频率{c:1, b:1, a:1};② 窗口右移一格[1,3]子串变成了bae ③ 注意观察新窗口bae和旧窗口cba中间重叠了ba ④ 此时我们只需把刚离开窗口的左边字符c的计数减1。把刚进入窗口的新字符e的计数加1 ⑤ 经过两步简单的加减法sCount 数组变成了{b:1, a:1, e:1}这正是新窗口bae的频率代码实现如下classSolution{publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length();intpLenp.length();// 1. 边界处理如果 s 比 p 还短不可能存在异位词直接返回空列表if(sLenpLen){returnnewArrayListInteger();}ListIntegerresultnewArrayListInteger();// 2. 初始化两个频率统计数组长度为 26 对应 26 个小写英文字母int[]sCountnewint[26];int[]pCountnewint[26];// 3. 构建初始窗口统计 p 的字母频率以及 s 中前 pLen 个字母频率for(inti0;ipLen;i){// s.charAt(i) - a可将字符映射为数组索引。a的ASCII 值为 97sCount[s.charAt(i)-a];pCount[p.charAt(i)-a];// 此时sCount 记录了 s 中第一个窗口内各字母出现的频率pCount 记录了目标字符串的字母频率}// 4. 检查 初始窗口 是否匹配if(Arrays.equals(sCount,pCount)){result.add(0);}// 5. 核心滑动过程窗口从索引 1 开始一直滑动到 s 的末尾for(inti0;isLen-pLen;i){// 【出】窗口左边界字符离开将 s[i] 的计数减 1--sCount[s.charAt(i)-a];// 【进】窗口右边界新字符进入将 s[i pLen] 的计数加 1sCount[s.charAt(ipLen)-a];// 6. 比较当前窗口与目标字符串 p 的频率是否一致if(Arrays.equals(sCount,pCount)){// 注意此时窗口的起始索引是 i 1result.add(i1);}}returnresult;}}提交代码运行结果如下滑动窗口法 复杂度分析时间复杂度O(N)其中 N 是字符串 s 的长度M 为字符串 p 的长度初始化两个数组和初始窗口需要 O(M) 滑动窗口过程需遍历 O(N−M) 次每次操作加减计数 比较 26 个元素都是 O(1) 总体来看时间复杂度与 s 的长度成线性关系。空间复杂度O(1)仅使用了两个固定大小为 26 的整型数组 sCount 和 pCount以及几个辅助变量不随输入数据的规模增长。
