Substring with Concatenation of All Words

Q:
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).
A:
哦，这道题，一开始是理解错了题目意思了。
仔细研读要求。是对每一个substring,例如从0 开始的，还有从9开始的substring（长度为L的总长度），  里面包含了L里的所有的non-intervening 组合。就是把所有的L的string连起来。
例如，上面例子中从0 开始的: barfoo 就是L的一个组合。 同样，从9开始的，foobar 也是一个组合。
假设L 里一共有n个string，每个string 长度为 m 
分析：
1：我们不能穷尽L的组合形式。 2^n
2:  我们如果从每一个节点都开始计算L， 有点儿太啰嗦的感觉。 想想有没有什么好方法，来跳过部分预先监测的结果。
3： NOTE: strings in L， might exist replication.
4:  初步设想，用一个 list  记录所有match 的节点。然后看后面的substring是否match。     这样，问题就归结于该list里面的值，是否能凑够0到n-1个match。--------但这里有个问题，就是L中 可能有重复的情况。需要注意对待。
（问题就归结到，一个list，每个点包含了match的位置，如果全部的，都有0到n-1都能match的话，就加入result中，否则 移动到下一个点。）

class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        res = []
        import copy 
        if len(words) == 0:
            return res
        wLen = len(words[0])
        origD = {} # cannot use set(), since words might have duplicates
        for w in words:
            self.add2Dict(w,origD)
            
        for i in range(wLen):
            D = copy.deepcopy(origD)
            foundD = {}
            # check every possible starting position, to see whether it is a match
            startIndex = i # the index that not valid 
            for end in range(i, len(s) - wLen +1, wLen):
                # continue adding, till we find a match
                substr = s[end:end+wLen]
                if substr in D: # in original dict
                    self.add2Dict(substr,foundD)
                    self.removeD(substr,D)
                    if len(D) == 0:
                        res.append(startIndex)
                        topStr = s[startIndex: startIndex + wLen]
                        self.add2Dict(topStr, D)
                        self.removeD(topStr,foundD)
                        startIndex += wLen
                        
                elif substr in foundD: # found, but have been removed before
                    while s[startIndex: startIndex+ wLen] != substr:
                        ss = s[startIndex: startIndex+wLen]
                        self.add2Dict(ss,D)
                        self.removeD(ss,foundD)
                        startIndex += wLen
                    startIndex += wLen
                    
                else: # not in words at all,  reset the whole
                    startIndex = end + wLen # next position is a good (or loop till right)
                    self.addD1toD2(foundD,D)
        return res     
    
    def removeD(self, word, D):
        if D[word] == 1:
            del D[word]
        else:
            D[word] = D[word] -1
    
    def add2Dict(self, word, D):
        if word not in D:
            D[word] = 1
        else:
            D[word] = D[word] + 1
    
    def addD1toD2(self, D1, D2): # merge two dict, into D2
        for k in D1:
            self.add2Dict(k,D2)
        D1.clear()

------------------------------4th pass----------------------------
思路：  因为允许重复，所以要记录下出现的次数，因此需要用HashMap.
       而这次，为了加速，我们在最外边的循环中，用了 基于各个起始点的位置。

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> list = new LinkedList<Integer>();
        if(S==null || L == null | S.length()==0 || L.length == 0)
            return list;
        // note that L might contains duplicates
        int n = S.length(), m = L[0].length(), k = L.length;
        HashMap<String, Integer> origMap = new HashMap<String,Integer>();
        for(int i= 0;i<L.length;i++){
            String str = L[i];
            int count = 1;
            if( origMap.containsKey(str)){
                count += origMap.get(str);
            }
            origMap.put(str,count);
        }
        for(int i =0;i<m;i++){ // for each possible starting position
            HashMap<String,Integer> tmpMap = new HashMap<String, Integer>();
            int j = i;
            while( j<= n-m ){
                // remove the oldest
                if( j-m*k>=0 ){
                    String oldStr = S.substring(j-m*k,j-m*k+m);
                    if(tmpMap.containsKey(oldStr)){
                        if(tmpMap.get(oldStr)>1){
                            tmpMap.put(oldStr,tmpMap.get(oldStr)-1);
                        }else{
                            tmpMap.remove(oldStr);
                        }
                    }
                }
                // add the newest
                String newStr = S.substring(j,j+m);
                int nFind = 1;
                if(tmpMap.containsKey(newStr)){
                    nFind += tmpMap.get(newStr);
                }
                tmpMap.put(newStr,nFind);
                // check if it is match
                boolean isAllFind = true;
                for(String str : origMap.keySet()){
                    if(tmpMap.containsKey(str)== false || tmpMap.get(str)!=origMap.get(str)){
                        isAllFind = false;
                        break;
                    }
                }
                if(isAllFind)
                    list.add(j-m*k+m);
                //update j
                j+=m;
            }
        }
        return list;
    }
}
 

--------------------第二遍----------- AC 了 --------
思路就是：  既然允许有重复， 而且， 还要尽量快， 用Set是不太行了。 那就用HashMap， 来记录下 每个key的出现的次数。

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        if (S == null || L == null || S.length() == 0 || L.length == 0)
            return al;
        // make a set from L, so that we can
        int nL = L.length;
        int mL = L[0].length();
        for (int k = 0; k <= S.length() - nL * mL; k++) {
            Map<String, Integer> map = buildSet(L);
            String curS = S.substring(k, k + mL * nL);
            int i = 0;
            int matchedCount = 0;
            while (matchedCount < nL) {
                String tmp = curS.substring(i, i + mL);
                if (map.containsKey(tmp)) {
                    int count = map.get(tmp);
                    if(count <=0)
                        break;
                    map.put(tmp, count - 1);
                    i += mL;
                    matchedCount++;
                } else 
                    break;
            }
            // iterator all the list, to see whether it has been fully visited
            boolean isAllFind = true;
            for(String key : map.keySet())
                if(map.get(key)>0){
                    isAllFind = false;
                    break;
                }
            if(isAllFind)
                al.add(k);
        }
        return al;
    }

    private Map<String, Integer> buildSet(String[] L) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < L.length; i++) {
            if (map.containsKey(L[i])) {
                int count = map.get(L[i]);
                map.put(L[i], count + 1);
            } else
                map.put(L[i], 1);
        }
        return map;
    }
}

Mistakes:
----------------第二遍------开始理解错题意了。
1：  所谓的withougt any interleaving characters,是指一个 concatenation里面不能interleaving. 但是，多个，是可以的。
2：  输入的  L  可以是["a","b","a"] ，  因此，不能用Set 来存储。





Learned:

---------------3 rd 想利用每个L 中的 string 映射到一个HashMap上去。------------
思想很简单， 和楼上的那个通不过的方法如出一致。-------------其实就是第二遍的思想。-------
           就是对每个string in L  ,map 一个数值。 作为标记。   然后，看其是否在map中出现过，如果出现过，对比出现的次数。

但是，还是suffer了这样一个问题， 就是L 中有重复的情况。
因此，我们还需要记录在L中出现的次数。   作为参照物，还要记录用过的次数。
因此，我们自己定义了一个类。

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        int n = L.length;// assume n > 0
        int l = L[0].length();
        HashMap<String, SNode> map = new HashMap<String, SNode>();
        int nDifferent=0; // number of different Strings in L
        for(int i =0;i< n;i++){
            SNode node = map.get(L[i]);
            if(node == null){
                nDifferent++;
                node = new SNode(nDifferent);
                map.put(L[i],node);
            }else
                node.count++;
        }
        // for each position, calculate its total sum
        for(int i =0;i<= S.length() - l*n; i++){
            for(int j =0;j< n;j++) // reset all 
                map.get(L[j]).nUsed=0;
            // test sum of these String
            boolean isBreak = false;
            for(int k = 0;k<n;k++){
                String str= S.substring(i+k*l, i+(k+1)*l);
                SNode node = map.get(str);
                if(node == null || node.nUsed>=node.count){
                    isBreak = true;
                    break;
                }else{
                    node.nUsed++;
                }
            }
            if(!isBreak)
                al.add(i);
        } 
        return al;
    }
    
}
class SNode{
    public int val;
    public int count;
    public int nUsed=0; // number of used
    public SNode(int v){
        val = v;
        count = 1;
    }
}