LC30. Substring with Concatenation of All Words

작성일

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

  • 일단 막가파식 $O(N\times {N \over K})$풀이로 풀어재끼니까 느리지만 답은 나옴
  • 좀더 빠른 풀이를 위해서는 $O(N)$으로 줄일 필요가 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(words.empty()) return {};
        
        int idx = 0;
        unordered_map<string, int> w2i;
        for(string& word : words)
            if(!w2i.count(word)) w2i[word] = idx++;
        
        vector<int> orig(w2i.size());
        for(string& word : words)
            orig[w2i[word]]++;
        
        int k = words[0].size();
        
        vector<int> ans;
        for(int i = 0; i < k; i++) {
            for(int j = i; j < s.size(); j+=k) {
                auto cnts = orig;
                int x;
                for(x = 0; x < words.size(); x++) {
                    string cur = s.substr(j+x*k,k);
                    if(w2i.count(cur)) {
                        cnts[w2i[cur]]--;
                        if(cnts[w2i[cur]] < 0) break;
                    } else {
                        j += x*k;
                        break;
                    }
                }
                if(x == words.size()) ans.push_back(j);
            }
        }
        return ans;
    }
};