71198d649cba758fc5a1323612539ec7
(难度Hard) Problem 30. Substring with Concatenation of All Words (母串匹配多串)

链接

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

难度等级

Hard

题干

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

题意

给定一个字符串s,和一个字符串的数组表示单词。要求,从s当中找到一个位置,使得从该位置开始,能够找到所有的单词。

注意:所有的单词长度相同

样例

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.


Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

题解

这道题的难度是Hard,讲道理,的确不简单。

所有的单词长度相同是一个非常重要而且又非常容易被忽视的条件,一旦没有这个前提,这个问题会变得非常困难。好在所有单词的长度是一样的,无论是从原串当中提取子串还是对比都要容易得多。

解法一 暴力对比

既然所有单词的长度相同,那么这个问题就变得简单多了。由于一个单词可能并不只出现一次,所以我们把所有的单词存入map,计算每一个单词的词库。然后枚举s串当中的起始位置,从起始位置开始,取出同样长度的子串,判断是否在词库当中。如果不在,则枚举下一个位置,否则则对比下一个子串。

写成伪代码:

def match(s, words):
    l = len(s)
    m = len(words[0])
    # 词库里单词数量
    words_cnt = 0
    # 构建单词库
    for word : words:
        if word not in voca:
            voca[word] = 0
        voca[word]++
        words_cnt++
    for i in range(l):
        j = i
        # 存储当前放入的单词
        cur = {}
        # 当前放入的单词数
        finish = 0
        while j < l:
            # 提取当前位置的子串
            word = s.substr(j, m)
            # 如果出现在词库当中,并且数量没有超过
            if word in voca and voca[word] > cur[word]:
                cur[word]++;
                finish++
            # 判断是否所有单词都已经放入
            if finish == words_cnt:
                ans.append(i)
                break
            j += m

这份伪代码加上一些边界条件判断,基本上就是最后提交的代码了。

```
class Solution {
public:
vector findSubstring(string s, vector& words) {
vector vt;
int l = s.size();
if (l==0 || words.size() == 0) return vt;
int m = words[0].size();

    map<string, int> mp;
    int wordsCnt = 0;
    for (string str : words) {
        if (mp.count(str) == 0) mp[str] = 0;
        mp[str]++;
        wordsCnt++;
    }

    for (int i = 0; i < l; i++) {
        map<string, int> cur;
        int wc = 0;
        for (int j = i; j < l; j+= m) {
            string sub = s.substr(j, m);
            if (mp.count(sub) && cur[sub] < mp[sub]) {
                cur[sub] ++;
                wc++;
            }else {
                cur.clear();
                break;
            }
top Created with Sketch.