Substring with Concatenation of

标签： C++ 算法 LeetCode 字符串

每日算法——leetcode系列

问题 Substring with Concatenation of All Words

Difficulty: 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.

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

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

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        
    }
};

翻译

与所有单词相关联的字串

难度系数：困难
给定一个字符串s和一些长度相同的单词words，找出s的与words中所有单词(words每个单词只出现一次)串联一起(words中组成串联串的单词的顺序随意)的字符串匹配的所有起始索引，子串要与串联串完全匹配，中间不能有其他字符。

思路

这题对我来说就是理解题意。
先把words中每个单词，以words中每个单词为key, 单词出现的次数为value放入map表中
再在s中每次取三个来去map表找，如果找到则找下三个，如果没找到，则s索引回溯到找到的第一个的索引 + 1。

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string> &words) {
        
        vector<int> result;
        if (s.size() <= 0 || words.size() <= 0) {
            return result;
        }
        
        if (s.size() < words.size() * words[0].size()) {
            return result;
        }
        
        int m = static_cast<int>(s.size());
        int n = static_cast<int>(words.size());
        int l = static_cast<int>(words[0].size());
        
        unordered_map<string, int> wordMap;
        for (int i = 0; i < n; ++i) {
            if (wordMap.find(words[i]) != wordMap.end()) {
                wordMap[words[i]]++;
            } else {
                wordMap[words[i]] = 1;
            }
        }
        
        unordered_map<string, int> bakWordMap = wordMap;
        int fisrtIdnex = 0;
        for (int j = 0; j <= m - l;) {
            string word = s.substr(j, l);
            if (wordMap.find(word) == wordMap.end()) {
                j = ++fisrtIdnex;
                wordMap = bakWordMap;
                continue;
            }
            j += l;
            wordMap.at(word)--;
            if (wordMap.at(word) == 0) {
                wordMap.erase(word);
            }
            
            if (wordMap.empty()) {
                result.push_back(fisrtIdnex);
                wordMap = bakWordMap;
            }
        }
        
        return result;
    }

};

注： 这个本地测试可以， 但提交提示超时， 再考虑下其他的办法。