仙游网站建设公司,云南网络推广公司,千牛商家版网站建设,中核二三建设有限公司目录 1.题目2.答案3.提交结果截图4.图解 链接#xff1a; 串联所有单词的子串 1.题目
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如#xff0c;如果 w… 目录 1.题目2.答案3.提交结果截图4.图解 链接 串联所有单词的子串 1.题目
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [ab,cd,ef] 那么 abcdef abefcdcdabef cdefabefabcd 和 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 10^41 words.length 50001 words[i].length 30words[i] 和 s 由小写英文字母组成 2.答案
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger result new ArrayList();int wordLength words[0].length();int wordCount words.length;for (int i 0; i wordLength; i) {// 超出长度if (i wordCount * wordLength s.length()) {break;}// 初始化窗口MapString, Integer map new HashMap();for (int j 0; j wordCount; j) {String word s.substring(i j * wordLength, i (j 1) * wordLength);map.put(word, map.getOrDefault(word, 0) 1);}// 筛掉原单词数组for (String word : words) {map.put(word, map.getOrDefault(word, 0) - 1);if (map.get(word) 0) {map.remove(word);}}// 滑动窗口for (int j 0; i j wordCount * wordLength s.length(); jwordLength) {if (j ! 0) {String addWord s.substring(i j wordLength * (wordCount - 1), i j wordLength * wordCount);map.put(addWord, map.getOrDefault(addWord, 0) 1);if (map.get(addWord) 0) {map.remove(addWord);}String delWord s.substring(i j - wordLength, i j);map.put(delWord, map.getOrDefault(delWord, 0) - 1);if (map.get(delWord) 0) {map.remove(delWord);}}if (map.size() 0) {result.add(i j);}}}return result;}
}3.提交结果截图 4.图解
以如下测试用例举例说明
输入s barfoothefoobarman, words [foo,bar]
输出[0,9]首先可以将字符串 s 按照单词长度进行划分通过开头跳过字符长度的方式可以分为以下三种划分方式。 以划分方式1举例可以将所有单词总长度单词数 * 单词长度来作为一个窗口从左往右滑动。 最终得到的 index0 和 index9 就是我们的结果了。
整理完毕完结撒花~
