每日算法——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
    
      findSubstring(string s, vector
     
      & words) {            }};
     
    

翻译

与所有单词相关联的字串

难度系数：困难

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

思路

这题对我来说就是理解题意。

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

代码

class Solution {public:    vector
    
      findSubstring(string s, vector
     
       &words) {                vector
      
        result;        if (s.size() <= 0 || words.size() <= 0) {            return result;        }                if (s.size() < words.size() * words[0].size()) {            return result;        }                int m = static_cast
       
        (s.size());        int n = static_cast
        
         (words.size());        int l = static_cast
         
          (words[0].size()); unordered_map
          
            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
           
             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; }};
           
          
         
        
       
      
     
    

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