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
題目描述：與所有單詞相關(guān)聯(lián)的子串
給定一個(gè)子串s和一些長(zhǎng)度相同的單詞組成的字符串?dāng)?shù)組words.
注意：
在s中找出恰好串聯(lián)words中所有單詞的子串的起始位置,中間不能有其他字符，但不要考慮words中單詞串聯(lián)的順序.
示例1：(允許無(wú)序)
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">由題意，我們可以得到以下幾點(diǎn)信息：</font>
- 找到的子串長(zhǎng)度等于給定單詞數(shù)組長(zhǎng)度與其中單個(gè)字符串長(zhǎng)度的乘積
- 單詞數(shù)組里面允許出現(xiàn)重復(fù)的單詞
- 子串之間是可以疊加出現(xiàn)的（示例3）
解法一：
- 首先中鼠，我們可以得到words中單個(gè)字符的長(zhǎng)度喉悴，設(shè)為
wLen,words字符串?dāng)?shù)組的長(zhǎng)度為wordsLen; - 找到的子串長(zhǎng)度必定為
wLen * wordsLen; - 遍歷給定字符串,長(zhǎng)度為
sLen,可以得到sLen-wLen * wordsLen+1個(gè)子串; - 遍歷時(shí)，將長(zhǎng)度為
wLen * wordsLen的子串等均等拆分為字符串?dāng)?shù)組,每個(gè)字符串長(zhǎng)度為wLen; - 將上一步得到的字符串?dāng)?shù)組進(jìn)行排序猛遍，給定的words也要進(jìn)行排序，這時(shí)候，如果兩個(gè)字符串?dāng)?shù)組的內(nèi)容一樣睡腿，則該子串符合要求，將子串對(duì)應(yīng)的索引添加到返回的結(jié)果數(shù)組中.
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);
}
}
當(dāng)然峻贮，這樣的算法屬于一種暴力求解席怪，復(fù)雜度最佳和最差都是n * log2(n)
如下圖：
image
