leetcode:Substring with Concatenation of All Words

Question:

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).

给定一个字符串S，并且给定list类型的几个单词L，每个单词长度相等。找到L中的每个单词组合在一起的单词在S中的起始下标，在这个组合中，不能加入其它任何非L中的单词或字母，例子如

S: "barfoothefoobarman"
L: ["foo", "bar"]

应该返回[0,9] 顺序不是问题。

算法思路：1、把L中的单词放入Map中，名字为words，名为用来记录每个单词出现的次数，tempwords用来记录临时取得的字符串以及相对应数量。

　　　　　2、从S中的第一个字符开始，不断截取字符串str，如果words中不包括所要截取的字符串str,循环中断;如果tempwords中得到的字符串str出现的个数已经大于words中字符串str个数，则中断。(详见代码)

代码设计：

 1 class Solution29 {
 2     
 3     public ArrayList<Integer> findSubstring(String S, String[] L) {
 4         Map<String,Integer> words=new HashMap<String,Integer>();
 5         Map<String,Integer> tempwords=new HashMap<String,Integer>();
 6         ArrayList<Integer> arraylist=new ArrayList<Integer>();//记录下标
 7         if(L.length<=0)
 8             return arraylist;
 9         //记录L中每个单词的次数
10         for(int i=0;i<L.length;i++){
11             if(words.containsKey(L[i])){
12                 int temp=words.get(L[i]);
13                 words.put(L[i],temp+1);
14             }
15             else{
16                 words.put(L[i], 1);
17             }
18         }
19         
20         int N=L.length;//数组L含有字符串的个数
21         int M=L[0].length();//数组L中每个字符串的长度
22         for(int i=0;i<=S.length()-N*M;i++){
23             tempwords.clear();
24             int j;
25             for( j=0;j<N;j++){
26                 String str=S.substring(i+j*M, i+j*M+M);
27                 if(!words.containsKey(str))
28                     break;
29                 if(tempwords.containsKey(str)){
30                     int temp=tempwords.get(str);
31                     tempwords.put(str,temp+1);
32                 }
33                 else{
34                     tempwords.put(str, 1);
35                 }
36                 if(tempwords.get(str)>words.get(str))
37                     break;
38             }
39             
40             if(j==N)
41                 arraylist.add(i);
42             
43         }
44         return arraylist;
45     }
46 }

2013-12-10