[LeetCode # 30] Substring with Concatenation of All Words

문자열 s 와, 각각이 동일한 길이를 갖는 단어들 words 가 주어졌을 때 words 를 모두 연결해서 나올 수 있는 substring 을 찾는 문제

예를 들어, s 가 "barfoothefoobarman" 이고 words 가 ["foo","bar"] 이면 words 를 모두 연결했을 때 나올 수 있는 문자열은 "foobar" 와 "barfoo" 두 가지이다. 문자열 s에서 위 문자열은 다음과 같이 나타난다. "barfoothefoobarman". 이 때 반환값은 문자열 s에서 찾고자 하는 문자열 words 의 결합이 나타나는 곳의 시작 위치이다.

 

이 문제에서 중요한 것은, words 의 결합된 문자열의 시작 위치가 어떤 순서로 반환되는 지는 상관이 없다는 점이다. 문제를 해결하기 위해 생각한 방법은 주어진 words 에서 각각의 word 의 등장 횟수를 저장하고, s 를 순차적으로 탐색하면서 해당 위치에서 부분 문자열이 words 에 주어진 word 중 하나인지, 맞다면 count 값을 증가시켜 각 word 별로 등장 횟수가 words 에서 얻은 정보와 일치하는 지를 확인한다.

 

이와 같은 풀이로 작성한 코드는 다음과 같다.

 

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> indexes;
        unordered_map<string, int> counts;
        for (auto word : words) {
            counts[word]++;
        }
        int len = s.length(), n = words.size(), wordLen = words[0].length();
        for (int i = 0; i < len - n * wordLen + 1; i++){
            unordered_map<string, int> seen;
            int j;
            for (j = 0; j < n; j++){
                string word = s.substr(i + j * wordLen, wordLen);
                if (counts.find(word) != counts.end()) {
                    seen[word]++;
                    if (seen[word] > counts[word])
                        break;
                }
                else
                    break;
            }
            if (j == n)
                indexes.push_back(i);
        }
        return indexes;
    }
};

 

위의 코드는 매 탐색 별로 이전 탐색의 정보를 이용하지 않지만, 보완할 수 있다면 위의 코드를 Sliding Window 기법을 활용해 이전 탐색에 이어서 탐색을 이어갈 수 있도록 하면 성능 면에서 더 효율적으로 동작할 수 있을 것 같다.