微网站的建设,地方门户网站建设要求,天眼查询个人信息官网,云南网站建设哪个好从0开始的秋招刷题路#xff0c;记录下所刷每道题的题解#xff0c;帮助自己回顾总结
30. 串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。…从0开始的秋招刷题路记录下所刷每道题的题解帮助自己回顾总结
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 10410^4104 1 words.length 5000 1 words[i].length 30 words[i] 和 s 由小写英文字母组成
采用滑动窗口方法解题解题思路类似最小覆盖子串这里只是把字符换成了单词。这里有个需要注意的点因为字符串不一定是单词长度的倍数所以指针开始滑动的位置不能只有0而是需要考虑整个单词长度的情况。比如
输入: linglikabba[ab, ba]
输出: [7]这里如果指针从0开始滑动的话就找不到匹配的结果了但是他确实是有输出的。这里的指针应该从1开始滑动就可以得到结果了。
在每次遍历的开始都需要将窗口清空并把匹配数初始化为0。
class Solution {public ListInteger findSubstring(String s, String[] words) {int left 0, right 0, len 0;// 所有单词数int size words.length;ListInteger res new ArrayList(10);// 如果目标数组为空则返回一个空集合if (words.length 0){return res;}else{// 单词长度len words[0].length();}// 定义两个map集合一个存目标单词一个存滑动窗口MapString, Integer needs new HashMap(5);MapString, Integer windows new HashMap(10);// 初始化目标集合将单词与出现的次数对应存入map集合中for (int i 0; i words.length; i){// 如果单词存在集合中则返回出现的次数否则返回0int count needs.getOrDefault(words[i], 0);// 存入map中次数1needs.put(words[i], count 1);}// 单词的匹配数量包括单词和出现次数int match 0;// 由于字符串不一定是单词长度的倍数所以需要遍历一个单词长度的所有情况for (int i 0; i len; i ){// 初始化左右指针开始处为imatch初始化为0right left i;match 0;// 右指针最多到字符串的最后一个单词开始位置while(right s.length() - len){// 向右滑动存入单词和出现的次数String s1 s.substring(right, right len);// 以单词长度为步长移动右指针right len;int count windows.getOrDefault(s1, 0);windows.put(s1, count 1);// 如果单词和出现的次数与目标一致则匹配1if (needs.containsKey(s1) windows.get(s1).intValue() needs.get(s1).intValue()){match ;}// 当匹配数等于目标集合的大小说明已经覆盖了目标集合while (left right match needs.size()) {// right - left / len求出窗口中单词数如果等于目标单词数则匹配成功将左指针位置加入listif ((right - left) / len size) {res.add(left);}// 左指针右移类似右指针方法String s2 s.substring(left, left len);left len;windows.put(s2, windows.get(s2) - 1);if (needs.containsKey(s2) windows.get(s2).intValue() needs.get(s2).intValue()){match --;}}}// 清空窗口进行下一次遍历windows.clear();}return res;}
}
