[hard] 30. Substring with Concatenation of All Words

문제

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

Substring with Concatenation of All Words - LeetCode

---

풀이방법

silding window 방법으로 시도했으나 접근방법이 잘못되서 계속 예외케이스들이 나와서 실패.

결국 다른사람 풀이 보고 이해해서 풀었다.

words의 단어들의 길이는 모두 동일하고, words의 단어들이 한번씩 전부 등장해야 한다는 조건이 굉장히 중요했다. 

 

그리고 첫 단어의 시작점이 s의 맨 앞이 아닐수도 있기 때문에, 다양한 시작점을 고려해주기 위해 left의 시작점을 0~wlen으로 지정했다.

아래의 예시에서 left가 0에서 시작해서 wlen 만큼 이동하면서 체크할 경우, 1번과 4번은 제대로 체크가 되지만 2번과 3번은 체크되지 않는다.

이런 경우를 해결하기 위해 left의 시작 범위를 0~wlen으로 지정한 것이다.

 

그리고 나서는 wlen씩 이동하면서 범위 내에 있는 문자열이 words의 단어에 해당하는지 체크한다.

words 의 단어들에 중복이 허용되므로 단어별 등장횟수를 wcnt로 관리한다.

wlen 범위 내의 문자열에 해당하는 단어가 wcnt에 있을 경우, 몇 번 나왔는지 체크를 위해 wcnt에서 해당 단어에 -1 처리를 해준다.

 

이 때 words에 없는 단어가 등장하거나, 단어가 words에 보다 여러번 등장했다면 지금까지 체크했던 단어들을 재정비 해야한다.

아래의 예시에서 'foo'는 한번만 등장해야하는데, s[0:3]에 이미 'foo'가 나온 상태에서 s[3:6]에 다시 'foo'가 나온다. 

그래서 left를 기준으로 앞에서부터 이전에 등장했던 단어들을 체크하면서 'foo'가 한번만 나올때까지 left를 이동시키고, wcnt도 +1 해서 복구시켜준다.

 

이렇게 반복하다가 left와 right의 간격이 wlen * len(words) 가 되면 모든 단어가 한번씩 등장했다는 의미가 되므로, result에 left 값을 추가한다.

반응형

---

코드

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        result = []
        wlen = len(words[0])
        
        for left in range(wlen): # 단어의 시작이 맨 앞이 아닐수도 있기 때문에 다양한 시작점을 고려해주기 위함
            wcnt = collections.Counter(words)
            
            for right in range(left + wlen, len(s) + 1, wlen):
                w = s[right-wlen:right]
                wcnt[w] -= 1
                while wcnt[w] < 0: # words 리스트에 없는 단어가 포함되었거나, 단어가 words보다 많은 횟수만큼 등장했다는 의미
                    wcnt[s[left:left+wlen]] += 1
                    left += wlen
                    
                if left + wlen * len(words) == right:
                    result.append(left)
        
        return result