[LeetCode] 030. Substring with Concatenation of All Words (Hard) (C++/Java)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github: https://github.com/illuz/leetcode

030. Substring with Concatenation of All Words (Hard)

链接：

题目：https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/
代码(github)：https://github.com/illuz/leetcode

题意：

给一个字符串 S 和一个单词列表，单词长度都一样，找出所有 S 的子串，子串由所有单词组成，返回子串的起始位置。

分析：

很明显每个子串都是由所有单词组成的，长度是一定的，所以直接枚举子串，切分后再用 map 进行判断就行了。

这样的算法复杂度是 O(n*m)，其实还有几种很酷的 O(n) 的算法：

1. 跟「076. Minimum Window Substring (Hard)」 一样的思路，就是维护两个指针，分别为前后区间，和一个 map，跑前面的指针看看当前区间能不能恰好匹配，行的话就得到答案了。
2. 还有个用神奇的 map<string, queue> 来做，其实原理是跟 1 是一样的，具体见：code with HashTable with Queue for O(n) runtime
3. 这其实只是一个优化，在匹配时使用 Trie 匹配，具体见：Accepted recursive solution using Trie Tree

这里用 C++ 实现了 O(n*m) 算法，用 Java 实现了 1 算法。

代码：

C++:

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
		map<string, int> words;
		map<string, int> curWords;
		vector<int> ret;
		int slen = S.length();
		if (!slen || L.empty()) return ret;
		int llen = L.size(), wlen = L[0].length();
		
		// record the current words map
		for (auto &i : L)
			++words[i];

		// check the [llen * wlen] substring
		for (int i = 0; i + llen * wlen <= slen; i++) {
			curWords.clear();
			int j = 0;
			// check the words
			for (j = 0; j < llen; j++) {
				string tmp = S.substr(i + j * wlen, wlen);
				if (words.find(tmp) == words.end())
					break;
				++curWords[tmp];
				if (curWords[tmp] > words[tmp])
					break;
			}
			if (j == llen)
				ret.push_back(i);
		}
		return ret;
    }
};

Java:

public class Solution {

    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> ret = new ArrayList<Integer>();
        int slen = S.length(), llen = L.length;
        if (slen <= 0 || llen <= 0)
            return ret;
        int wlen = L[0].length();

        // get the words' map
        HashMap<String, Integer> words = new HashMap<String, Integer>();
        for (String str : L) {
            if (words.containsKey(str)) {
                words.put(str, words.get(str) + 1);
            } else {
                words.put(str, 1);
            }
        }

        for (int i = 0; i < wlen; ++i) {
            int left = i, count = 0;
            HashMap<String, Integer> tmap = new HashMap<String, Integer>();

            for (int j = i; j <= slen - wlen; j += wlen) {
                String str = S.substring(j, j + wlen);

                if (words.containsKey(str)) {
                    if (tmap.containsKey(str)) {
                        tmap.put(str, tmap.get(str) + 1);
                    } else {
                        tmap.put(str, 1);
                    }

                    if (tmap.get(str) <= words.get(str)) {
                        count++;
                    } else {
                        // too many words, push the 'left' forward
                        while (tmap.get(str) > words.get(str)) {
                            String tmps = S.substring(left, left + wlen);
                            tmap.put(tmps, tmap.get(tmps) - 1);
                            if (tmap.get(tmps) < words.get(tmps)) {
                                // if affect the count
                                count--;
                            }
                            left += wlen;
                        }
                    }

                    // get the answer
                    if (count == llen) {
                        ret.add(left);
                        // it's better to push forward once
                        String tmps = S.substring(left, left + wlen);
                        tmap.put(tmps, tmap.get(tmps) - 1);
                        count--;
                        left += wlen;
                    }
                } else {
                    // not any match word
                    tmap.clear();
                    count = 0;
                    left = j + wlen;
                }
            }
        }
        return ret;
    }
}