串联所有单词的子串

采用散列表和动态规划，中间查找相同的字符串可以适当优化（我这里没优化但能够通过）。

var findSubstring = function(s, words) {
    var ans = [];
    let maps = [];
    let dp = [];
    let same = [];
    let k = words[0].length;
    let n = s.length;
    for(let i = 0; i < words.length; i++) {
        maps[words[i]] = maps[words[i]] == undefined ? 1 : maps[words[i]]+1;
    }
    for(let i = -k; i < 0; i++) {
        dp[i] = 0;
    }
    for(let i = 0; i < s.length; i++) {
        let m_k = '';
        for(let j = 0; j < k; j++) {
            m_k = m_k + s[i+j];
        }
        if(maps[m_k] == undefined) {
            dp[i] = 0;
        } else {
            if(same[m_k] == undefined) {
                same[m_k] = [];
                dp[i] = dp[i - k] + 1;
            } else {
                let count = dp[i - k];
                let find = -1;
                let start = i;
                let sc = 1;
                if(same[m_k].length < maps[m_k] && count >= same[m_k].length) {
                    dp[i] = dp[i - k] + 1;
                } else {
                    while(count > 0) {
                        start -= k;
                        if(same[m_k].indexOf(start) >= 0) {
                            sc++;
                            if(maps[m_k] < sc) {
                                find = dp[i-k] - count;
                                break;
                            }
                        }
                        count--;
                    }
                    if(find == -1) { 
                        dp[i] = dp[i - k] + 1;
                    }
                    else {
                        dp[i] = find + 1;
                    }
                }
            }
            if(dp[i] >= words.length) { 
                ans.push(i - (dp[i] - 1) * k ); 
            }
            same[m_k].push(i);
        }
    }
    return ans;
};