[leetcode]Substring with Concatenation of All Words

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

算法思路：

1. 遍历S，每遇到一个字符，就取出wordLength的长度，并验证是否在L中，如不在，i++，如在，进行loop迭代，直到找到一个concatenation （记录下来）或者失配。继续i++，时间复杂度最好为O(n)，最坏为O(n* num * wordLength)

 1 public class Solution {
 2     List<Integer> list = new ArrayList<Integer>();
 3     public List<Integer> findSubstring(String S, String[] L) {
 4         int num = L.length;
 5         int wordLength = L[0].length();
 6         if(S.length() < wordLength * num) return list;
 7         HashMap<String,Integer> hash = new HashMap<String,Integer>();
 8         for(int i = 0; i < L.length; i++){
 9             if(hash.containsKey(L[i])) hash.put(L[i],hash.get(L[i]) + 1);
10             else hash.put(L[i],1);
11         }
12         HashMap<String,Integer> copy = new HashMap<String,Integer>(hash);
13         for(int i = 0; i <= S.length() - wordLength; i++){
14             int start = i;
15             int end = start + wordLength;
16             String sub = S.substring(start, end); 
17             if(copy.get(sub)!=null && copy.get(sub) != 0){
18                 int count = 0;
19                 boolean canLoop = true;
20                 while(canLoop){
21                     copy.put(S.substring(start, end), copy.get(S.substring(start, end)) - 1);
22                     count++;
23                     if(count == num){
24                         list.add(i);
25                         copy = (HashMap<String,Integer>)hash.clone();
26                         break;
27                     }
28                     start = end;
29                     end += wordLength;
30                     if(end > S.length() || !copy.containsKey(S.substring(start, end)) || copy.get(S.subSequence(start, end).toString()) <= 0){
31                         canLoop = false;
32                         copy = (HashMap<String,Integer>)hash.clone();
33                     }
34                 }
35             }
36         }
37         return list;
38     }
39 }

思路2：

优化，双指针法，思想类似 Longest Substring Without Repeating Characters，复杂度可以达到线性。（待验证）

第二遍记录：

跟第一遍的思路1一样，代码也差不多：

 1 public class Solution {
 2     public List<Integer> findSubstring(String s, String[] l) {
 3         List<Integer> res = new ArrayList<Integer>();
 4         if(l == null || l.length == 0 || s == null || s.length() < l.length * l[0].length())  return res;
 5         Map<String,Integer> map = new HashMap<String,Integer>();
 6         for(String str : l){
 7             if(map.get(str) == null){ 
 8                 map.put(str,1);
 9             }else{ 
10                 map.put(str,map.get(str) + 1);
11             }
12         }
13         Map<String,Integer> cpy = new HashMap<String,Integer>(map);
14         int wordLength = l[0].length();
15         for(int i = 0; i <= s.length() - wordLength * l.length; i++){
16             String head = s.substring(i,i + wordLength);
17             if(!cpy.containsKey(head)) continue;
18             boolean valid = true;
19             for(int j = 0; j < l.length; j++){
20                 String word = s.substring(i + j * wordLength, i + j * wordLength + wordLength);
21                 if(!cpy.containsKey(word) || cpy.get(word) == 0) {
22                     valid = false;
23                     cpy = new HashMap<String,Integer>(map);
24                     break;
25                 }else{
26                     cpy.put(word, cpy.get(word) - 1);
27                 }
28             }
29             if(valid){
30                 res.add(i);
31                 cpy = new HashMap<String,Integer>(map);
32             }
33         }
34         return res;
35     }
36 }

View Code

参考链接：

http://blog.csdn.net/ojshilu/article/details/22212703

http://blog.csdn.net/linhuanmars/article/details/20342851