---

thumbnail: https://s2.ax1x.com/2019/04/05/ARfLq0.jpg
title: 30.Substring with Concatenation of All Words(续)
toc: true
tags: leetcode
categories: leetcode
comments: true

---

题目描述：与所有单词相关联的子串

      给定一个子串s和一些长度相同的单词组成的字符串数组words.
注意：
      在s中找出恰好串联words中所有单词的子串的起始位置,中间不能有其他字符，但不要考虑words中单词串联的顺序.
上篇我们讨论了本题的一种暴力求解法，本篇接着讨论另外两种优化的解法.

---

解法二：

      本方法遍历子串时，同解法一不同之处在于，子串与给定单词字符串数组words的匹配规则不同.解法一是利用子串组成的数组和给定words的排序结果的内容相同来判断子串是否满足要求;而解法二利用了map，首先将words中单词与单词频次转化为key-value的形式，遍历s时得到的子串按同理存于另一个map里面，判断这两个map是否相等，以此决定该子串是否满足要求。

---

java源程序：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int sLen = s.length();
        int unit = words.length;
        List<Integer> res = new LinkedList<>();
        if(unit==0 || sLen==0) return res;
        int wLen = words[0].length();
        int wordsLen = unit*wLen;
        Map<String,Integer> map = new HashMap<>();

        for(String word:words){
            map.put(word,map.getOrDefault(word,0)+1);

        }

        for(int i=0;i<sLen-wordsLen+1;i++){
            Map<String,Integer> temp = new HashMap<>(map);
            int j=0;
            for(;j<unit;j++){
                String sub = s.substring(i+j*wLen,i+(j+1)*wLen);
                if(!temp.containsKey(sub)||temp.get(sub)==0) break;
                temp.put(sub,temp.get(sub)-1);

            }
            if(j==unit) res.add(i);

        }
    }
}

运行时间和空间如下图：

解法二时间空间复杂度

---

解法三：

      解法三与解法二判断子串和words是否匹配的方法一样，但是遍历子串的方式有所不同.在第一层循环中，以一个字符为单位，遍历次数为wLen,在第二层循环中，以wLen为一单位，比较当前子串第一个长度为wLen的单词与其后长度为wLen的单词是否相同，相同就维持未来字符串不变，这样，如果匹配成功的话，索引位置就对应于子串首次出现的位置;如果不同，删除子串第一个单词，加入子串后的一个单词，形成一个新的子串.两层循环下，可以将所有的情况遍历完，重要的是，第二层循环的处理减少了map的频繁操作，从而降低了时间的复杂度。

---

java源程序：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int sLen = s.length();
        int unit = words.length;
        List<Integer> res = new LinkedList<>();
        if(unit==0 || sLen==0) return res;
        int wLen = words[0].length();
        int wordsLen = unit*wLen;
        Map<String,Integer> map = new HashMap<>();
        for(String word:words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        for(int i=0;i<wLen;i++){
            Map<String,Integer> temp = new HashMap<>();
            for(int k=0;k<unit&&i+(k+1)*wLen<=sLen;k++){
                String sub = s.substring(i+k*wLen,i+(k+1)*wLen);
                temp.put(sub,temp.getOrDefault(sub,0)+1);
            }
            if(map.equals(temp)) res.add(i);
            for(int j=i+wordsLen;j+wLen<=sLen;j+=wLen){
                String start = s.substring(i,i+wLen);
                String end = s.substring(j,j+wLen);
                temp.put(end,temp.getOrDefault(end,0)+1);
                if(temp.get(start)==1) temp.remove(start);
                else temp.put(start,temp.get(start)-1);
                i += wLen;
                if(map.equals(temp)) res.add(i);
            }
            i%=wLen;
        }
        return res;
    }   
}

运行时间和空间如下图：

解法三时间空间复杂度