首页 > 代码库 > Leetcode | Substring with Concatenation of All Words

Leetcode | Substring with Concatenation of All Words

2024-07-04 02:42:10   226人阅读

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

这题真是自作孽不可活啊。一直想用动态规划去做，但是一旦L里面有重复词就很麻烦。花了几个小时还是没做出来啊。。。我可怜的周末。

网上一看，原来就是扫描每一个位置，从该位置开始对每个单词计数。map里面存的是每个单词出现的次数（可能大于1）。

注意点：

1. S.length()返回值是size_t，如果直接用S.length()-int的话，负数会被转成很大的数；所以以后记得取字符串大小时，用一个int先来存。(Line 9)；

2. 用一个map统计word list中每个单词出现的次数； (Line 10-13)

3. 从第i个位置开始，用一个map来统计每个单词出现的次数，该次数不能超过第2步得到的次数；(Line 19)；

4. 如果最终合法的单词总数等于L.size()的话，把i存到结果中；（Line 25)。

 1 class Solution {
 2 public:
 3     vector<int> findSubstring(string S, vector<string> &L) {
 4         vector<int> ret;
 5         if (S.empty()) return ret;
 6         if (L.empty()) return ret;
 7         int len = L[0].size();
 8         int wholeLen = len * L.size();
 9         int n = S.length();
10         map<string, int> wordCount;
11         for (int j = 0; j < L.size(); ++j) {
12             wordCount[L[j]]++;
13         }
14         for (int i = 0; i <= n - wholeLen; ++i) {
15             string tmp = S.substr(i, len);
16             int pos = i;
17             int c = 0;
18             map<string, int> exist;
19             while (wordCount.count(tmp) > 0 && exist[tmp] < wordCount[tmp]) {
20                 c++;
21                 pos += len;
22                 exist[tmp]++;
23                 tmp = S.substr(pos, len);
24             }
25             if (c == L.size()) ret.push_back(i);
26         }
27         return ret;
28     }
29     
30 private:
31     
32 };

 

 


联系
我们