上海网站推广维新,页面模版 公众号,用花生壳做网站速度可以吗,仿卢松松博客网站源码【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主#xff0c;题解使用C语言。#xff08;若有使用其他语言的同学也可了解题解思路#xff0c;本质上语法内容一致题解使用C语言。若有使用其他语言的同学也可了解题解思路本质上语法内容一致 【题目描述】
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [ab,cd,ef] 那么 abcdef abefcdcdabef cdefabefabcd 和 efcdab 都是串联子串。 acdbef 不是串联子串因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
【示例一】
输入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] 也是可以的。
【示例二】
输入s wordgoodgoodgoodbestword, words [word,good,best,word]
输出[]
解释因为 words.length 4 并且 words[i].length 4所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
【示例三】
输入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 10的4次方1 words.length 50001 words[i].length 30words[i] 和 s 由小写英文字母组成
【代码】
// 滑动窗口class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger res new ArrayList();int num words.length;// 单词的长度int wordLen words[0].length();// 字符串长度int stringLen s.length();for (int i 0; i wordLen; i) {// 遍历的长度超过了整个字符串的长度退出循环if (i num * wordLen stringLen) {break;}// differ表示窗口中的单词频次和words中的单词频次之差MapString, Integer differ new HashMap();// 初始化窗口窗口长度为num * wordLen,依次计算窗口里每个切分的单词的频次for (int j 0; j num; j) {String word s.substring(i j * wordLen, i (j 1) * wordLen);differ.put(word, differ.getOrDefault(word, 0) 1);}// 遍历words中的word对窗口里每个单词计算差值for (String word : words) {differ.put(word, differ.getOrDefault(word, 0) - 1);// 差值为0时移除掉这个wordif (differ.get(word) 0) {differ.remove(word);}}for (int start i; start stringLen - num * wordLen 1; start wordLen) {if (start ! i) {// 右边的单词进来String word s.substring(start (num - 1) * wordLen, start num * wordLen);differ.put(word, differ.getOrDefault(word, 0) 1);if (differ.get(word) 0) {differ.remove(word);}// 左边的单词出去word s.substring(start - wordLen, start);differ.put(word, differ.getOrDefault(word, 0) - 1);if (differ.get(word) 0) {differ.remove(word);}word s.substring(start - wordLen, start);}// 窗口匹配的单词数等于words中对应的单词数if (differ.isEmpty()) {res.add(start);}}}return res;}
}
