Leetcode: 30. Substring with Concatenation of All Words

Description

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.

Example

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

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

思路

• 這題做得我蛋疼。做的時候，一直考慮優化優化，提交的時候才發現，這有特麽情況太多了，優化個屁啊，優化半天還是800多ms
• 自己的具體思路就不寫了，貼個代碼出來
• 網上搬一個大佬的代碼吧。唉。

代碼

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

        if (s.empty() || words.empty()) return res;

        unordered_map<string, int> hashMap;
        unordered_map<string, int> copyMap;
        unordered_map<string, int> cmpMap;
        int len = words[0].size(), sumLen = 0;
        for (int i = 0; i < words.size(); ++i){
            hashMap[words[i]]++;
            cmpMap[words[i]] = 0;
            sumLen += words[i].size();
        }
        copyMap = hashMap;

        int i = 0, sum = 0;
        string tmp;
        int flag = 1, curLen = 0, start = 0;
        while (i < s.size()){
            sum = 0;
            tmp = s.substr(i, len);
            if (copyMap.find(tmp) == copyMap.end()){
                start++;
                flag++;
                curLen = 0;
                hashMap = copyMap;
                i = start;
            }
            else{
                if (cmpMap[tmp] == flag){
                    if (hashMap[tmp] == 0){
                        hashMap = copyMap;
                        start++;
                        curLen = 0;
                        ++flag;
                        i = start;
                    }
                    else{
                        hashMap[tmp]--;
                        curLen += len;
                        i += len;
                    }   
                }
                else{
                    cmpMap[tmp] = flag;
                    hashMap[tmp]--;
                    curLen += len;
                    i += len;
                }
            }

            if (curLen == sumLen){
                res.push_back(start);
                start++;
                curLen = 0;
                flag++;
                i = start;
                hashMap = copyMap;
            }
        }

        return res;
    }
   
};

• 分析一個大佬的代碼

  class Solution {
  public:
   vector<int> findSubstring(string s, vector<string>& words) {
      vector<int> res;
  
      if (s.empty() || words.empty() || s.size() < words[0].size()) return res;
  
      //一個用來保存原始字典，一個用來輔助
      unordered_map<string, int> hashMap;
      unordered_map<string, int> cmpMap;
      int num = words.size();
      int len = words[0].size();
      for (int i = 0; i < num; ++i){
          hashMap[words[i]]++;
      }
  
      int count = 0, start = 0;
      string tmp;
      //不需要從 0 - s.size() , 一個一個的遍歷過去，其實，只可能以0-len這些開頭，這是個重點，可以推的
      for (int i = 0; i < len; ++i){
          count = 0;
          //重置start 和 map
          start = i;
          cmpMap.clear();
  
          //每一次比較一個單詞，而不是一個字元一個字元的比
          for (int j = i; j <= s.size() - len; j += len){
              tmp = s.substr(j, len);
  
              //在裡面
              if (hashMap.find(tmp) != hashMap.end()){
                  cmpMap[tmp]++;   
  
                  //當前單詞可能在結果裡面
                  if (cmpMap[tmp] <= hashMap[tmp]) count++;
                  else{
                     //當前單詞已經重覆了
                     //從start 開始減，把前面加進來的都減出去
                      while (cmpMap[tmp] > hashMap[tmp]){
                          string strTemp = s.substr(start, len);
                          cmpMap[strTemp]--;
                          if (cmpMap[strTemp] < hashMap[strTemp])
                              count--;
                          start += len;
                      }
                  }
  
                  //保存結果
                  if (count == num){
                      res.push_back(start);
  
                      cmpMap[s.substr(start, len)]--;
                      start += len;
                      count--;
                  }
              }
              else{
                  //不在字典中，重新開始
                  cmpMap.clear();
                  start = j + len;
                  count = 0;
              }
          }
      }
      return res;
  }
  };

• 大佬的代碼學到了很多，但是現在確實是沒時間展開分析了。。