[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

题意

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

分析

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

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

  1. 跟「076. Minimum Window Substring (Hard)」 1样的思路,就是保护两个指针,分别为前后区间,和1个 map,跑前面的指针看看当前区间能不能恰好匹配,行的话就得到答案了。
  2. 还有个用奇异的 map<string, queue> 来做,其实原理是跟 1 是1样的,具体见:code with HashTable with Queue for O(n) runtime
  3. 这其实只是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;
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » [LeetCode] 030. Substring with Concatenation of All Words (Hard) (C++/Java)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡