Skip to content

30.substring with concatenation of all words

难度Hard

刷题内容

原题连接

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

内容描述

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 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 = "wordgoodstudentgoodword",
  words = ["word","student"]
Output: []

思路 **- 时间复杂度: O(mlgn)*- 空间复杂度: O(m+n)***

这题可以两个 map 来解决,第一个 map 中存放了 words 中的所有单词和出现的次数,接下来遍历字符串,固定区间的大小为 words 的长度,存入另一个map,两个 map 相等就放入返回数组中

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        if(!s.length() || !words.size())
            return ans;
        unordered_map<string,int> m1;
        int len = words.size(),wl = words[0].length(),sl = s.length();
        for(int i = 0;i < words.size();++i)
            m1[words[i]]++;
        int count1 = 0,reLen = wl * len,left = 0;
        for(int i = 0;i < sl - wl * len + 1;++i)
        {
            unordered_map<string,int> m2;
            for(int j = 0,left = i;j < len;j ++)
            {
                string temp = s.substr(left,wl);
                left += wl;
                m2[temp]++;
            }
            if(m2 == m1)
                ans.push_back(i);
        }
        return ans;
    }
};


回到顶部