[LeetCode] 030. Substring with Concatenation of All Words (Hard) (C++/Java)
來源：程序員人生 發布時間：2015-03-12 09:23:04 閱讀次數：2946次
索引：[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
題意：
給1個字符串 S 和1個單詞列表，單詞長度都1樣，找出所有 S 的子串，子串由所有單詞組成，返回子串的起始位置。
分析：
很明顯每一個子串都是由所有單詞組成的，長度是1定的，所以直接枚舉子串，切分后再用 map 進行判斷就好了。
這樣的算法復雜度是 O(n*m)，其實還有幾種很酷的 O(n) 的算法：
- 跟「076. Minimum Window Substring (Hard)」 1樣的思路，就是保護兩個指針，分別為前后區間，和1個 map，跑前面的指針看看當前區間能不能恰好匹配，行的話就得到答案了。
- 還有個用奇異的
map<string, queue> 來做，其實原理是跟 1 是1樣的，具體見：code with HashTable with Queue for O(n) runtime - 這其實只是1個優化，在匹配時使用 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;
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
