[LeetCode] 030. Substring with Concatenation of All Words (H

索引：[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) 的算法：

这里用 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 mapfor (auto &i : L)++words[i];// check the [llen * wlen] substringfor (int i = 0; i + llen * wlen <= slen; i++) {curWords.clear();int j = 0;// check the wordsfor (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' mapHashMap<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' forwardwhile (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 countcount–;}left += wlen;}}// get the answerif (count == llen) {ret.add(left);// it's better to push forward onceString tmps = S.substring(left, left + wlen);tmap.put(tmps, tmap.get(tmps) – 1);count–;left += wlen;}} else {// not any match wordtmap.clear();count = 0;left = j + wlen;}}}return ret;}}

发光并非太阳的专利，你也可以发光