Leetcode: 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"]

这道题想的时候颇费了一些周折，想过把L的所有concatenation组合出来，放到hash或map里，然后遍历S的时候直接看。但是这样如果L的size： Lsize过大的话，可能的组合有Lsize！种，组合数剧增，效率低下，所以不采用这种方法。

又考虑在S中从左向右一个word一个word遍历过去，一次只取L中一个word的大小，存入Hashmap，如果匹配到了L，则算找到了一种可能的concatenation；这样也有缺点，比如L为foo the kgm tim cog, S为bar foo tim cog kgm tim foo the, S遍历到第二个tim时出现不匹配，所以我的指针得跳到第一个tim的下一个，才能不漏掉所有的可能性。我要想跳到第一个tim得存下它的位置，这就要求hashmap的value为元素位置，这就导致我不好进行匹配，因为L若要存为一个hashmap，它的value我无法确定

所以参考网上有了第三种做法，先把L中的word存入一个Hashmap， 记录每个word的出现次数，然后在S中从左向右挨个遍历过去，每次取wsize * Lsize个字母分成Lsize份存入Hashmap中，每份大小为wsize, 然后比较这个Hashmap与L的Hashmap是否一致

import java.util.*;

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (S.length() == 0 || L.length == 0) return result;
        Hashtable<String, Integer> obj = new Hashtable<String, Integer>();
        Hashtable<String, Integer> real = new Hashtable<String, Integer>();
        int Lsize = L.length;
        int wsize = L[0].length();
        for (String a : L) {
            if (obj.containsKey(a)) {
                int k = obj.get(a);
                obj.put(a, k+1);
            }
            else obj.put(a, 1);
        }
        
        for (int i = 0; i <= S.length() - Lsize * wsize; i++) {
            real.clear();
            for (int j = 0; j <= Lsize - 1; j++) {
                String temp = S.substring(i + j * wsize, i + (j+1) * wsize);
　　　　　　　　　　　if (!obj.containsKey(temp)) break;
                if (real.containsKey(temp)) {
                    int m = real.get(temp);
                    real.put(temp, m+1);
                }
                else real.put(temp, 1);
            }
            if (real.equals(obj)) {
                result.add(i);
            }
        }
        
        return result;
    }
}

 另一个版本，也许更好懂一点

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        HashMap<String, Integer> target = new HashMap<String, Integer>();
        HashMap<String, Integer> real = new HashMap<String, Integer>();
        for (String str : L) {
            if (target.containsKey(str)) {
                int val = target.get(str);
                target.put(str, val+1);
            }
            else {
                target.put(str, 1);
            }
        }
        
        int wSize = L[0].length();
        int lSize = L.length;
        for (int i=0; i<=S.length()-lSize*wSize; i++) {
            for (int j=i; j<=i+lSize*wSize-1; j=j+wSize) {
                String temp = S.substring(j, j+wSize);
                if (!target.containsKey(temp)) break;
                if (real.containsKey(temp)) {
                    int value = real.get(temp);
                    real.put(temp, value+1);
                }
                else {
                    real.put(temp, 1);
                }
            }
            if (real.equals(target)) {
                res.add(i);
            }
            real.clear();
        }
        return res;
    }
}