vs2013做网站保存的格式,中国建设银行官网登录首页,域名申请了怎么做网站,西安网页设计师培训班题目链接
串联所有单词的子串
题目描述 注意点
words[i] 和 s 由小写英文字母组成1 words.length 5000可以以 任意顺序 返回答案words中所有字符串长度相同
解答思路
根据滑动窗口哈希表解决本题#xff0c;哈希表存储words中所有的单词及单词的出现次数#…题目链接
串联所有单词的子串
题目描述 注意点
words[i] 和 s 由小写英文字母组成1 words.length 5000可以以 任意顺序 返回答案words中所有字符串长度相同
解答思路
根据滑动窗口哈希表解决本题哈希表存储words中所有的单词及单词的出现次数滑动窗口时使用另一个哈希表存储当前窗口内已经出现的单词及单词的出现次数因为words中所有字符串长度相同所以在移动滑动窗口右边界时应该以单词为维度每次移动wordLen个单位然后判断该部分单词rightWord是否能作为串联串联所有单词的子串的一部分有以下三种情况 如果rightWord根本不属于words中的单词说明包含该单词时的子串一定不满足题意此时需要将滑动窗口直接移动到该单词右侧也就是直接重置滑动窗口的左右边界如果rightWord属于words中的单词但是当前滑动窗口中该单词数量已经达到words中该单词的最大数量此时需要移动滑动窗口的左边界移动时每次也同样移动wordLen个单位直到左侧找到一个与rightWord相同的值leftWord一定能找到将滑动窗口左边界移动到leftWord右侧如果rightWord属于words中的单词且当前滑动窗口中该单词数量还未超过words中该单词的最大数量此时满足题意继续移动滑动窗口右边界注意判断该滑动窗口已经是串联所有单词的子串的情况 上述过程并未判断所有情况因为每次移动边界时都是以wordLen为单位如果从字符串首位置开始可能会忽略1,2…(wordLen - 1)为起始位置的情况观察规律可得只需要对1,2…(wordLen - 1)为起始位置都执行一次上述的操作就可以考虑到所有的情况
代码
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger res new ArrayList();int wordSum words.length;int wordLen words[0].length();if (s.length() wordSum * wordLen) {return res;}MapString, Integer map new HashMap();for (String word : words) {map.put(word, map.getOrDefault(word, 0) 1);}for (int i 0; i wordLen; i) {int left i;int right i;int currWordSum 0;MapString, Integer visitedMap new HashMap();while (right wordLen s.length()) {// 长度越界剩下的子串一定无法串联所有单词if (left (wordSum - currWordSum) * wordLen s.length()) {break;}String leftWord s.substring(left, left wordLen);String rightWord s.substring(right, right wordLen);// 该单词不存在则有该单词的部分都一定不满足题意将滑动窗口左边界移动至该单词右侧if (map.get(rightWord) null) {left right wordLen;visitedMap new HashMap();currWordSum 0;}// 该单词存在但words中已经没有该单词if (map.get(rightWord) ! null visitedMap.getOrDefault(rightWord, 0) map.get(rightWord)) {while (left right !rightWord.equals(leftWord)) {visitedMap.put(leftWord, visitedMap.get(leftWord) - 1);left wordLen;leftWord s.substring(left, left wordLen);currWordSum--;}left wordLen;}// 该单词存在满足题意if (map.get(rightWord) ! null visitedMap.getOrDefault(rightWord, 0) map.get(rightWord)) {visitedMap.put(rightWord, visitedMap.getOrDefault(rightWord, 0) 1);currWordSum;// 已找到串联所有单词的子串if (currWordSum wordSum) {res.add(left);visitedMap.put(leftWord, visitedMap.get(leftWord) - 1);currWordSum--;left wordLen;}}right wordLen;}}return res;}
}关键点
滑动窗口的思想移动滑动窗口时其对应的哈希表的变化移动滑动窗口右边界时对应单词是否是串联所有单词的子串的三种情况
