邯郸企业做网站,北京行业网站制作,优化门户网站建设,python软件开发#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 滑动窗口 哈希表 求解思路 实现代码 运行结果 共勉 题目链接
30. 串联所有单词的子串
⛲ 题目描述
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [“ab”,“cd”,“ef”] 那么 “abcdef” “abefcd”“cdabef” “cdefab”“efabcd” 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1
输入s “barfoothefoobarman”, words [“foo”,“bar”] 输出[0,9] 解释因为 words.length 2 同时 words[i].length 3连接的子字符串的长度必须为 6。 子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。 子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。 示例 2
输入s “wordgoodgoodgoodbestword”, words [“word”,“good”,“best”,“word”] 输出[] 解释因为 words.length 4 并且 words[i].length 4所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。 示例 3
输入s “barfoofoobarthefoobarman”, words [“bar”,“foo”,“the”] 输出[6,9,12] 解释因为 words.length 3 并且 words[i].length 3所以串联子串的长度必须为 9。 子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。 子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。 子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。
提示
1 s.length 104 1 words.length 5000 1 words[i].length 30 words[i] 和 s 由小写英文字母组成 求解思路实现代码运行结果 ⚡ 滑动窗口 哈希表 求解思路
该题暴力解法肯定是通过不了的所以我们需要使用其它的解法。该题是438. 找到字符串中所有字母异位词的进阶版本依旧是通过滑动窗口Hash表来解决只不过该题需要使用词频表来维护单词出现的次数而基础题维护的是字符出现的次数。使用哈希表 wordsMap 记录 words 中每个单词的出现次数枚举 s 中的每个字符作为起点往后取长度为len * n的子串 str使用哈希表 strMap 统计 str 每个单词的出现次数每隔 w 长度作为一个单词比较 wordsMap 和 strMap 是否相同实现代码如下所示 实现代码
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger ans new ArrayList();HashMapString, Integer wordsMap new HashMap();int n words.length, len words[0].length();int total len * n;for (String word : words) {wordsMap.put(word, wordsMap.getOrDefault(word, 0) 1);}int m s.length();for (int i 0; i m - total; i) {String str s.substring(i, i total);HashMapString, Integer strMap new HashMap();for (int j 0; j str.length(); j len) {String temp str.substring(j, j len);if (!wordsMap.containsKey(temp))break;strMap.put(temp, strMap.getOrDefault(temp, 0) 1);}if (wordsMap.equals(strMap))ans.add(i);}return ans;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
