[Two Pointer + Sliding Window 문제] LEETCODE 30. Substring with Concatenation of All Words

문제풀이

이번 문제는 Two Pointer 방식으로 해결하였다. 우선 left,right 범위를 정의하는 l,r변수를 선언하고 그 범위 내에서 탐색을 진행하는 p 변수를 선언하였다.
탐색 과정에서 크게 3가지 케이스에서 처리를 해주는 부분이 핵심이었는데 첫번째 부분은 현재 타겟이 되는 단어가 word 배열에 포함되는 경우, 두번째는 현재 타겟이 되는 단어가 word 배열에 존재하지만 중복 탐색인 경우 세번째는 타겟이 되는 단어가 word배열에 없는 경우이다.

[1] word 배열에 포함된 경우(중복X)
word 배열에 포함된 단어라면 매핑 단어 수 변수인 cnt에 대해 +1 처리한다. 만약 cnt 값이 len(word)와 동일하다면 모두 매핑이 된 케이스이므로 정답 배열에 인덱스 정보를 저장한다.

[2] word 배열에 포함된 경우(중복O)
word 배열에 포함된 단어이지만 이미 중복이 되었다면
중복 대상 문자열이 l,r 범위 내 가장 작은 인덱스 값을 산출한다. 해당 인덱스에 대해서 Window Size 만큼을 더한 값으로 l 인덱스를 업데이트한다. 즉 탐색 범위의 시작 값을 변경한다. 이는 추후 cnt 값이 len(word)와 동일하게 되면 정답 배열에 추가하게 되는 값이다.
단 여기서 중요한 것은 l을 update 하였다고 해서 l부터 다시 탐색하는 것은 불필요한 중복 탐색이 발생한다. 이전 중복이 발생했던 상황으로 돌아가면 l~p까지는 모두 word 배열에 존재하였다고 탐색이 되었던 상황이다. l~p까지가 모두 word 배열에 있다면 l+window size~p까지도 모두 word배열에 있다고 추론할 수 있다. 그러므로 재탐색은 p부터 진행하여도 속도를 최적화하여 해결 가능하다.

[3] word 배열에 포함되지 않은 경우
l,r 범위를 설정한 후 p 값을 탐색하다가 배열에 존재하지 않는 문자를 발견한 경우라면 이전에 탐색했던 단어가 배열에 있더라도 중간에 word 내 존재하지 않는 단어가 있다면 연속성이 깨지게 되므로 l,p,r 모두 window size 만큼 이동하여 탐색을 진행한다.

간략히 도식화하면 아래와 같다

코드

from collections import Counter
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        def search(l, p, r, dic_memo, dic_idx, cnt):
            word_freq = Counter(words)

            while True:
                if r > len(s):
                    break
                target_s = s[p:r]
                if target_s not in words:
                    cnt = 0
                    dic_memo = word_freq
                    dic_idx = {}
                    search(p + len_word, p + len_word, p + 2 * len_word, dic_memo, dic_idx, cnt)
                    break

                if dic_memo[target_s] == 0:
                    min_target_s_idx = dic_idx[target_s][0]

                    for i in range(l, min_target_s_idx + 1, len_word):
                        dic_memo[s[i:i+len_word]] += 1
                        dic_idx[s[i:i+len_word]].pop(0)
                        cnt -= 1

                    search(min_target_s_idx + len_word, p, p + len_word, dic_memo, dic_idx, cnt)
                    break

                if target_s in words:
                    if target_s in dic_idx: 
                        dic_idx[target_s].append(p)
                    else:
                        dic_idx[target_s] = [p]
                    dic_memo[target_s] -= 1
                    cnt += 1

                    if cnt == len_ans:
                        ans.append(l)
                        dic_memo[s[l:l+len_word]] += 1
                        dic_idx[s[l:l+len_word]].pop(0)
                        cnt -= 1
                        search(l + len_word, p + len_word, p + len_word * 2, dic_memo, dic_idx, cnt)
                        break

                l = l
                p = p + len_word
                r = r + len_word

        len_ans, len_word = len(words), len(words[0])        
        ans = []
        
        for i in range(len_word):
            l, p, r = 0, 0, len_word  
            dic_memo = Counter(words)
            dic_idx = {}            
            cnt = 0
            search(l + i, p + i, r + i, dic_memo, dic_idx, cnt)
        return ans


---- 소스 클린 버전
from collections import Counter
from typing import List

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        word_count = Counter(words)
        word_len, num_words = len(words[0]), len(words)
        total_len = word_len * num_words
        ans = []

        for i in range(word_len):
            left, right = i, i
            current_count = Counter()

            while right + word_len <= len(s):
                word = s[right:right + word_len]
                current_count[word] += 1
                right += word_len

                while current_count[word] > word_count[word]:
                    current_count[s[left:left + word_len]] -= 1
                    left += word_len

                if right - left == total_len:
                    ans.append(left)

        return ans

Lookback

1. 처음 해당 문제를 판단하였을 때 메모이제이션 + DFS 방식으로 해결이 가능할 것으로 보여 이 컨셉으로 문제를 접근하였는데 진행하다 보니 마치 Two Pointer 와 유사한 방식으로 해결하였다. 사실 함수를 재귀적으로 탐색할 필요도 없고 생각해보면 r 변수도 불필요한 부분이 있었다. 중간에 컨셉이 바뀌어서 그런지 소스 자체를 지저분하게 개발한 듯 하여 아쉬움이 컸다.