[Sliding Window][Hard] 30. Substring with Concatenation of All Words

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

 

Q. 문자열 s와 단어 배열 words가 주어질 때, words를 조합해서 구성할 수 있는 문자열이 s에 존재하면, 그 시작 위치 index를 반환하라.

 

 

Solution. 

 우선 문자열을 확인 할 frequency buffer가 hash type으로 필요하다. 

 그리고 sub string을 left to right 로 sliding 해 가면서 check 한다. 

 

 도중에 실패하면, 바로 다음 위치에서 시작한다. 

 성공한 문자를 찾아도 시작지점 바로 다음 위치에서 시작한다. 

 

 로직을 코드로 작성한다.

bool IsStartWith(string s, int idxStart, string word)
{
    if(word.Length>s.Length-idxStart) return false;

    for(int c = 0; c < word.Length; ++c) 
    {
        if(s[c+idxStart] != word[c])
            return false;
    }
    return true;
}

public IList<int> FindSubstring(string s, string[] words) 
{
    Dictionary<string, int> dictFreq = new Dictionary<string, int>();
    for(int k = 0; k < words.Length; ++k)
    {
        if(dictFreq.ContainsKey(words[k]))
            dictFreq[words[k]]++;
        else 
            dictFreq.Add(words[k], 1);
    }

    IList<int> listRet = new List<int>();

    Dictionary<string, int> curFreq = new Dictionary<string, int>(dictFreq);
    int left = 0, right = 0;
    for(; right < s.Length; )
    {
        bool found = false;
        foreach(var key in curFreq.Keys)
        {
            if(IsStartWith(s, right, key))
            {
                if(left < 0)    left = right;

                --curFreq[key];
                if(curFreq[key] == 0)
                    curFreq.Remove(key);

                if(curFreq.Count == 0)
                {
                    listRet.Add(left);
                    found = false;
                }
                else 
                {
                    found = true;
                    right += key.Length;
                }
                break;
            }
        }

        if(!found)
        {
            curFreq = new Dictionary<string, int>(dictFreq);
            right = left>-1 ? left : right;
            left = -1;
            ++right;
        }
    }
    return listRet;
}

 

 

일단은 결과를 얻었다.

 

Note: 결과는 얻었지만, sliding window category 관점에서 보면 오답에 가까운 풀이... 

frequency data를 reset 하지 않고 유지하면서 jump하게 되면 더 좋을 결과를 얻으리라 생각된다.