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中单词串联的顺序.

示例1：(允许无序)

Input:
       s = "barfoothefoobarman",
       words = ["foo","bar"]
Output:
       [0,9]

示例2：(中间不能有其他字符)

Input:
       s = "wordgoodgoodgoodbestword",
       words = ["word","good","best","word"]
Output:
       []

示例3：

Input:
       s = "oooooo",
       words = ["oo","oo"]
Output:
       [0,1,2]

<font color="red">由题意，我们可以得到以下几点信息：</font>

• 找到的子串长度等于给定单词数组长度与其中单个字符串长度的乘积
• 单词数组里面允许出现重复的单词
• 子串之间是可以叠加出现的（示例3）

解法一：

1. 首先，我们可以得到words中单个字符的长度，设为wLen,words字符串数组的长度为wordsLen;
2. 找到的子串长度必定为wLen * wordsLen;
3. 遍历给定字符串,长度为sLen,可以得到sLen-wLen * wordsLen+1个子串;
4. 遍历时，将长度为wLen * wordsLen的子串等均等拆分为字符串数组,每个字符串长度为wLen;
5. 将上一步得到的字符串数组进行排序，给定的words也要进行排序，这时候，如果两个字符串数组的内容一样，则该子串符合要求，将子串对应的索引添加到返回的结果数组中.

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;
        Arrays.sort(words);
        for(int i=0;i<sLen-wordsLen+1;i++){           
            String sub = s.substring(i,i+wordsLen);
            if(isSubstring(sub,unit,wLen,words)){
                res.add(i);
            }
        }
        return res;
    }
    public boolean isSubstring(String sub,int unit,int wLen,String[] words){
        
        String[] temp = new String[unit];
        for(int i=0,k=0;i<unit;i++){
            temp[i] = sub.substring(k,k+wLen);
            k = k+wLen;  
        }
        Arrays.sort(temp);
        return Arrays.equals(temp,words);
    }
}

当然，这样的算法属于一种暴力求解，复杂度最佳和最差都是n * log₂(n)
如下图：

image