[leetcode]Substring with Concatenation of All Words

代码写的很乱。参考的思路和昨天的Minimum Window Substring有类似。参考的文章是：http://discuss.leetcode.com/questions/210/substring-with-concatenation-of-all-words

代码里还特意把字符串转成数字id用来简化，这个优化不是必须的，没有的话代码会简单点。

一开始是用字典计数，然后穷举。后来时间不过，就只能用Min Window类似的双指针扫描的思路优化，保证一遍下来。差不多是O(n)的复杂度。

又看了一下我和参考中代码的区别，由于受到昨天的影响，我还在计算每个字符（串）超出的情况，其实现在只要记录全部的字符串数n就行了，维持一个窗口，因为肯定是连续的，这样代码可以简化许多。

我的代码：

import java.util.ArrayList;
import java.util.HashMap;
 
public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if (L.length == 0) return ret;
 
        HashMap<String, Integer> ids = new HashMap<String, Integer>();
        HashMap<Integer, Integer> neededCount = new HashMap<Integer, Integer>();        
         
        int len = L[0].length();          
        int[] LL = new int[S.length() - len + 1];
         
        // convert S to LL
        for (int i = 0; i+len <= S.length(); i++) {
            String s = S.substring(i, i+len);
            if (!ids.containsKey(s)) {
                int id = ids.size() + 1;
                ids.put(s, id);
            }
            int id = ids.get(s);
            LL[i] = id;         
        }
         
        // init neededCount
        for (int i = 0; i < L.length; i++) {
            if (!ids.containsKey(L[i])) {
                return ret;
            }
            int id = ids.get(L[i]);
            if (neededCount.containsKey(id)) {
                int c = neededCount.get(id);
                neededCount.put(id, c+1);  
            }
            else {
                neededCount.put(id,  1);
            }
        }
         
        HashMap<Integer, Integer> currentCount = new HashMap<Integer, Integer>();
        for (int i = 0; i < len; i++) {
            currentCount.clear();
            int total = 0;
             
            int left = i;
            int right = left;
            while (right < LL.length) {
                int id = LL[right];
                if (!neededCount.containsKey(id)) {
                    right += len;
                    left = right;
                    currentCount.clear();
                    total = 0;
                    continue;
                }
                if (!currentCount.containsKey(id)) {
                    currentCount.put(id, 1);
                }
                else {                  
                    int c = currentCount.get(id);
                    if (c >= neededCount.get(id)) { // ==
                        // move left forward
                        while (left <= right) {                      
                            if (LL[left] == id) {
                                currentCount.put(id, c-1);
                                total--;
                                left += len;
                                break;
                            }
                            left += len;
                        }
                        if (left > right) {
                            right += len;
                            left = right;
                            currentCount.clear();
                            total = 0;
                            continue;
                        }
                    }
                    c = currentCount.get(id);
                    currentCount.put(id, c+1);
                }
                 
                total++;
                if (total == L.length) {
                    ret.add(left);                  
                    // move left forward
                    int l = LL[left];
                    int c = currentCount.get(l);
                    currentCount.put(l, c-1);
                    total--;
                    left += len;
                         
                }
                right+=len;
            }
        }
        return ret;
    }
}

参考代码：

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = S.size(), n = L.size(), len = L[0].size();
        map<string, int> ids;

        vector<int> need(n, 0);
        for (int i = 0; i < n; ++i) {
            if (!ids.count(L[i])) ids[L[i]] = i;
            need[ids[L[i]]]++;
        }

        vector<int> s(m, -1);
        for (int i = 0; i < m - len + 1; ++i) {
            string key = S.substr(i, len);
            s[i] = ids.count(key) ? ids[key] : -1;
        }

        vector<int> ret;
        for (int offset = 0; offset < len; ++offset) {
            vector<int> found(n, 0);
            int count = 0, begin = offset;
            for (int i = offset; i < m - len + 1; i += len) {
                if (s[i] < 0) {
                    // recount
                    begin = i + len;
                    count = 0;
                    found.clear();
                    found.resize(n, 0);
                } else {
                    int id = s[i];
                    found[id]++;
                    if (need[id] && found[id] <= need[id])
                        count++;

                    if (count == n)
                        ret.push_back(begin);

                    // move current window
                    if ((i - begin) / len + 1 == n) {
                        id = s[begin];
                        if (need[id] && found[id] == need[id])
                            count--;
                        found[id]--;
                        begin += len;
                    }
                }
            }
        }
        return ret;
    }
};