[LeetCode] 30. Substring with Concatenation of All Words

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

Substring with Concatenation of All Words - LeetCode

 

문제접근법 : words의 배열안에있는 모든 문자열을 순서관계없이 합쳤을때

s 의 부분문자열이 될수있는 인덱스를 찾는 문제입니다.

words[i] 의 모든길이는 같고 words[i]가 중복될수도 있습니다.

 

그리고 모든 부분문자열의 길이는 반드시

words[i].size() * words.size() 여야 s의 부분문자열이 될가능성이 있겠죠

 

그리고 시작포인트를 0~ words[i].size()-1 까지 시작하면서 words[i].size()로 늘려나가면서 찾아야합니다.

 

소스코드 :

 

class Solution {
public:
vector<int> findSubstring(string s, vector<string> &words)
{
    vector<int> res;
    unordered_map<string, int> m;
    for (string &t : words)
        m[t]++;
    int len = words[0].size();
    int cnt = words.size();
    int size = s.size();

    for (int i = 0; i < len; i++)
    {
        unordered_map<string, int> m2;
        for (int j = i; j < cnt * len; j += len)
        {
            m2[s.substr(j, len)]++;
        }
        if(m==m2)res.push_back(i);
        for (int j = len+i; j <= size - len * cnt; j += len)
        {
            if (--m2[s.substr(j - len, len)] == 0)
            {
                m2.erase(s.substr(j - len, len));
            }
            if (++m2[s.substr(j + len * (cnt - 1), len)] == 0)
            {
                m2.erase(s.substr(j + len * (cnt - 1), len));
            }
            if (m == m2)
                res.push_back(j);
        }
    }
    sort(res.begin(),res.end());
    return res;
}
};

 

궁금한점 혹은 모르는점

어떤질문이든 댓글은 언제나 환영입니다.