LeetCode刷题Java版030.串联所有单词的子串

作者：沉默王二
发布时间：2022-08-23T07:17:35.323+0800

---

030.串联所有单词的子串

题意

给定一个字符串s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

难度

困难

示例

输入：s = "barfoothefoobarman", words = ["foo","bar"]

解释：从下标 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。

分析

本题要求我们找出s中能够恰好包含所有words的子串的起始位置。

很容易就能想到一个暴力的办法，每次都在s中截取长度为words.length * 单词长度的串，然后，对这个串进行检验，看它是不是恰好由words里面的字符串构成，但是这样子的时间复杂度……，就是了，显然不是我们能够承受的时间复杂度，但没关系，我们先写一写，写完说不定就有更好的思路了。

class Solution {

        List res = new ArrayList<>();        int length = words.length * words[0].length();        Map<String,Integer> cnt = new HashMap<>();        for (String word : words) cnt.put(word, cnt.containsKey(word) ? cnt.get(word) + 1 : 1);        for(int i = 0;i <= s.length() - length;i++){            Map<String,Integer> com = new HashMap<>();            String temp = s.substring(i,i + length);            for( int j = 0;j < temp.length();j += words[0].length()){                String t = temp.substring(j,j + words[0].length());                if(!cnt.containsKey(t))                    break;                com.put(t,com.containsKey(t) ? com.get(t) + 1 : 1);            }            if(com.equals(cnt))                res.add(i);        }        return res;    }}

我们来观察一下上述的过程：

对于每个长度为 6 的子串（words = ["foo","bar"]），我们都要检验一次，但是可以注意到，第一次和第四次，本质上就是去掉了一个bar加上一个the，第二次和第五次，本质上就是去掉了一个arf加上一个hef，第三次和第六次，本质上就是去掉了一个rfo加上了一个efo。

所以……我们可以考虑将他们分成单词长度组来看看他们的性质？

这样子是不是就豁然开朗了？

分组之后，每次只需要添加一个单词，再删去一个单词就可以得到了下一次的状态，这样子就不用费劲的重新构造这个字符串了，只需要利用现在的字符串就可以得出下一次的字符串，同时，每次添加一个单词和删去一个单词的代价也不高，我们可以直接在删除和添加的时候，对Map进行统计，快速得出答案！

这样子是不是就相当于设立了一个窗口，在字符串s上，以单词长度/每次的速度在移动，从而统计出每次移动的贡献值？所以这也经常被称作滑动窗口。

代码实现如下：

class Solution {

        List res = new ArrayList<>();        int lengthOfWord = words[0].length();        Map<String,Integer> standing = new HashMap<>();        for(String word : words)    standing.put(word,standing.containsKey(word) ? standing.get(word) + 1 : 1);        for(int i = 0;i < lengthOfWord;i++){            Map<String,Integer> window = new HashMap<>();            for(int j = i;j <= s.length() - lengthOfWord;j += lengthOfWord){                String T = s.substring(j,j + lengthOfWord);                window.put(T,window.containsKey(T) ? window.get(T) + 1 : 1);                if(j >= i + words.length * lengthOfWord){                    int popPos = j - words.length * lengthOfWord;                    String popString = s.substring(popPos,popPos + lengthOfWord);                    window.put(popString,window.get(popString) - 1);                    if(window.get(popString) == 0)                        window.remove(popString);                }                if(standing.equals(window))                    res.add(j - (words.length - 1) * lengthOfWord);                //因为需要的是起始位置，所以当前位置减去字符串长度就可以了            }        }        return res;    }}

总结

本题虽然是一道困难题，但实际上在我们将暴力的方法写出来之后，稍加分析，就能感受到这其实也不算是 hard 级别，重要的是观察每次匹配之间的关联性，从而得出相应的优化方法。

力扣链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 690 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

030.串联所有单词的子串

题意

给定一个字符串s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

难度

困难

示例

输入：s = "barfoothefoobarman", words = ["foo","bar"]

解释：从下标 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。

分析

本题要求我们找出s中能够恰好包含所有words的子串的起始位置。

很容易就能想到一个暴力的办法，每次都在s中截取长度为words.length * 单词长度的串，然后，对这个串进行检验，看它是不是恰好由words里面的字符串构成，但是这样子的时间复杂度……，就是了，显然不是我们能够承受的时间复杂度，但没关系，我们先写一写，写完说不定就有更好的思路了。

class Solution {

        List res = new ArrayList<>();        int length = words.length * words[0].length();        Map<String,Integer> cnt = new HashMap<>();        for (String word : words) cnt.put(word, cnt.containsKey(word) ? cnt.get(word) + 1 : 1);        for(int i = 0;i <= s.length() - length;i++){            Map<String,Integer> com = new HashMap<>();            String temp = s.substring(i,i + length);            for( int j = 0;j < temp.length();j += words[0].length()){                String t = temp.substring(j,j + words[0].length());                if(!cnt.containsKey(t))                    break;                com.put(t,com.containsKey(t) ? com.get(t) + 1 : 1);            }            if(com.equals(cnt))                res.add(i);        }        return res;    }}

我们来观察一下上述的过程：

对于每个长度为 6 的子串（words = ["foo","bar"]），我们都要检验一次，但是可以注意到，第一次和第四次，本质上就是去掉了一个bar加上一个the，第二次和第五次，本质上就是去掉了一个arf加上一个hef，第三次和第六次，本质上就是去掉了一个rfo加上了一个efo。

所以……我们可以考虑将他们分成单词长度组来看看他们的性质？

这样子是不是就豁然开朗了？

分组之后，每次只需要添加一个单词，再删去一个单词就可以得到了下一次的状态，这样子就不用费劲的重新构造这个字符串了，只需要利用现在的字符串就可以得出下一次的字符串，同时，每次添加一个单词和删去一个单词的代价也不高，我们可以直接在删除和添加的时候，对Map进行统计，快速得出答案！

这样子是不是就相当于设立了一个窗口，在字符串s上，以单词长度/每次的速度在移动，从而统计出每次移动的贡献值？所以这也经常被称作滑动窗口。

代码实现如下：

class Solution {

        List res = new ArrayList<>();        int lengthOfWord = words[0].length();        Map<String,Integer> standing = new HashMap<>();        for(String word : words)    standing.put(word,standing.containsKey(word) ? standing.get(word) + 1 : 1);        for(int i = 0;i < lengthOfWord;i++){            Map<String,Integer> window = new HashMap<>();            for(int j = i;j <= s.length() - lengthOfWord;j += lengthOfWord){                String T = s.substring(j,j + lengthOfWord);                window.put(T,window.containsKey(T) ? window.get(T) + 1 : 1);                if(j >= i + words.length * lengthOfWord){                    int popPos = j - words.length * lengthOfWord;                    String popString = s.substring(popPos,popPos + lengthOfWord);                    window.put(popString,window.get(popString) - 1);                    if(window.get(popString) == 0)                        window.remove(popString);                }                if(standing.equals(window))                    res.add(j - (words.length - 1) * lengthOfWord);                //因为需要的是起始位置，所以当前位置减去字符串长度就可以了            }        }        return res;    }}

总结

本题虽然是一道困难题，但实际上在我们将暴力的方法写出来之后，稍加分析，就能感受到这其实也不算是 hard 级别，重要的是观察每次匹配之间的关联性，从而得出相应的优化方法。

力扣链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 690 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

030.串联所有单词的子串

题意

给定一个字符串s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

难度

困难

示例

输入：s = "barfoothefoobarman", words = ["foo","bar"]

解释：从下标 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。

分析

本题要求我们找出s中能够恰好包含所有words的子串的起始位置。

很容易就能想到一个暴力的办法，每次都在s中截取长度为words.length * 单词长度的串，然后，对这个串进行检验，看它是不是恰好由words里面的字符串构成，但是这样子的时间复杂度……，就是了，显然不是我们能够承受的时间复杂度，但没关系，我们先写一写，写完说不定就有更好的思路了。

class Solution {

        List res = new ArrayList<>();        int length = words.length * words[0].length();        Map<String,Integer> cnt = new HashMap<>();        for (String word : words) cnt.put(word, cnt.containsKey(word) ? cnt.get(word) + 1 : 1);        for(int i = 0;i <= s.length() - length;i++){            Map<String,Integer> com = new HashMap<>();            String temp = s.substring(i,i + length);            for( int j = 0;j < temp.length();j += words[0].length()){                String t = temp.substring(j,j + words[0].length());                if(!cnt.containsKey(t))                    break;                com.put(t,com.containsKey(t) ? com.get(t) + 1 : 1);            }            if(com.equals(cnt))                res.add(i);        }        return res;    }}

我们来观察一下上述的过程：

对于每个长度为 6 的子串（words = ["foo","bar"]），我们都要检验一次，但是可以注意到，第一次和第四次，本质上就是去掉了一个bar加上一个the，第二次和第五次，本质上就是去掉了一个arf加上一个hef，第三次和第六次，本质上就是去掉了一个rfo加上了一个efo。

所以……我们可以考虑将他们分成单词长度组来看看他们的性质？

这样子是不是就豁然开朗了？

分组之后，每次只需要添加一个单词，再删去一个单词就可以得到了下一次的状态，这样子就不用费劲的重新构造这个字符串了，只需要利用现在的字符串就可以得出下一次的字符串，同时，每次添加一个单词和删去一个单词的代价也不高，我们可以直接在删除和添加的时候，对Map进行统计，快速得出答案！

这样子是不是就相当于设立了一个窗口，在字符串s上，以单词长度/每次的速度在移动，从而统计出每次移动的贡献值？所以这也经常被称作滑动窗口。

代码实现如下：

class Solution {

        List res = new ArrayList<>();        int lengthOfWord = words[0].length();        Map<String,Integer> standing = new HashMap<>();        for(String word : words)    standing.put(word,standing.containsKey(word) ? standing.get(word) + 1 : 1);        for(int i = 0;i < lengthOfWord;i++){            Map<String,Integer> window = new HashMap<>();            for(int j = i;j <= s.length() - lengthOfWord;j += lengthOfWord){                String T = s.substring(j,j + lengthOfWord);                window.put(T,window.containsKey(T) ? window.get(T) + 1 : 1);                if(j >= i + words.length * lengthOfWord){                    int popPos = j - words.length * lengthOfWord;                    String popString = s.substring(popPos,popPos + lengthOfWord);                    window.put(popString,window.get(popString) - 1);                    if(window.get(popString) == 0)                        window.remove(popString);                }                if(standing.equals(window))                    res.add(j - (words.length - 1) * lengthOfWord);                //因为需要的是起始位置，所以当前位置减去字符串长度就可以了            }        }        return res;    }}

总结

本题虽然是一道困难题，但实际上在我们将暴力的方法写出来之后，稍加分析，就能感受到这其实也不算是 hard 级别，重要的是观察每次匹配之间的关联性，从而得出相应的优化方法。

力扣链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 690 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412