Substring with Concatenation of All Words

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

For example, given:
s:?"barfoothefoobarman"
words:?["foo", "bar"]

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

题目意思: 输入字符串S和列表L，L含有一组长度相同的单词。找出所有子串的开始下标，该子串由L的所有单词拼接而成，而且没有夹杂其他字符

?

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        Map<String, Integer> dict = new HashMap<String, Integer>();
        for (String l : L) {
            if (!dict.containsKey(l)) {
                dict.put(l, 0);
            }
            dict.put(l, dict.get(l)+1);
        }
         
        int len = L[0].length();
        int lenSum = len*L.length;
         
        List<Integer> list = new ArrayList<Integer>();
         
        for (int i=0; i<=S.length()-lenSum; i++) {
            Map<String, Integer> dictCopy = new HashMap<String, Integer>(dict);
            boolean flag = true; 
            for (int j=i; j<i+lenSum; j=j+len) {
                String s = S.substring(j, j+len);
                Integer num = dictCopy.get(s);
                if (num==null || num==0) {
                	flag = false;
                	break;
                }
                num--;
                dictCopy.put(s, num);
            }
            if (flag) {
            	list.add(i);
            }
        }
         
        return list;
    }
}

?

Substring with Concatenation of All Words

原文：http://hcx2013.iteye.com/blog/2217608