国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > [LeetCode] 030. Substring with Concatenation of All Words (Hard) (C++/Java)

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

来源:程序员人生   发布时间:2015-03-12 09:23:04 阅读次数:2785次

索引:[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; } }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生