Link

传送门

Problem

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 wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

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

Mean

给你一个字符串和一个字符串vector,vector中每个字符串长度相同。让你从s中找到所有的下标,使得从此下标开始出现vector中所有单词并且单词不重叠。

Analysis

注意到words数组中可能会有重复单词,用map保存每个单词出现的次数。枚举每个起点,统计每个单词的次数然后与之前的map比较即可。

Code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        unordered_map<string, int> cnt;
        for(auto &i : words)
            ++cnt[i];
        int N = words.front().size();
        int M = words.size();
        for(int i = 0; i + N * M <= s.size(); ++i) {
            unordered_map<string, int> cur;
            bool ok = true;
            for(int j = 0; j < M; ++j) {
                string t = s.substr(i + j * N, N);
                if(++cur[t] > cnt[t]) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                ans.push_back(i);
                //printf("%d!!!\n", i);
            }
        }
        return ans;
    }
};

int main() {
    Solution solu;
    string s = "barfoothefoobarman";
    vector<string> v = {"foo", "bar"};
    solu.findSubstring(s, v);
    return 0;
}

欢迎留言