串联所有单词的子串

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

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

思路分析：

• 因为单词长度固定的，我们可以计算出截取字符串的单词个数是否和 words 里相等，所以我们可以借用哈希表。
• 一个是哈希表是 words，一个哈希表是截取的字符串，比较两个哈希是否相等

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result=new LinkedList<>();
        if(s==null||words==null||s.length()==0||words.length==0){
            return result;
        }
        HashMap<String,Integer> map=new HashMap<>();
        for(String word:words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        int len=words.length;
        int slen=words[0].length();
        int rlen=len*slen;
        for(int i=0;i<s.length()-rlen+1;i++){
            String str=s.substring(i,i+rlen);
             HashMap<String,Integer> tmap=new HashMap<>();
            for(int j=0;j<rlen;j+=slen){
                String res=str.substring(j,j+slen);
                tmap.put(res,tmap.getOrDefault(res,0)+1);
            }
            if(map.equals(tmap)){
                result.add(i);
            }
        }
        return result;
    }
}

最后

以上就是淡定夕阳为你收集整理的串联所有单词的子串的全部内容，希望文章能够帮你解决串联所有单词的子串所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。