机关网站内容建设,亚马逊网站,广州知名网站建设后台管理便捷,足球比方类网站开发题目
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如#xff0c;如果 words [ab,cd,ef]#xff0c; 那么 …题目
给定一个字符串 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^4 1 words.length 5000 1 words[i].length 30 words[i] 和 s 由小写英文字母组成 题解
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger res new ArrayListInteger();int m words.length, n words[0].length(), ls s.length();for (int i 0; i n; i) {if (i m * n ls) {break;}MapString, Integer differ new HashMapString, Integer();for (int j 0; j m; j) {String word s.substring(i j * n, i (j 1) * n);differ.put(word, differ.getOrDefault(word, 0) 1);}for (String word : words) {differ.put(word, differ.getOrDefault(word, 0) - 1);if (differ.get(word) 0) {differ.remove(word);}}for (int start i; start ls - m * n 1; start n) {if (start ! i) {String word s.substring(start (m - 1) * n, start m * n);differ.put(word, differ.getOrDefault(word, 0) 1);if (differ.get(word) 0) {differ.remove(word);}word s.substring(start - n, start);differ.put(word, differ.getOrDefault(word, 0) - 1);if (differ.get(word) 0) {differ.remove(word);}}if (differ.isEmpty()) {res.add(start);}}}return res;}
}
来自力扣官方题解
