LeetCode - 30. Substring with Concatenation of All Words (python)

https://leetcode.com/problems/substring-with-concatenation-of-all-words/?envType=study-plan-v2&envId=top-interview-150

• 난이도: hard
• 알고리즘: sliding window

접근방법1 - 정렬 이용

• s의 길이가 10,000이므로 O(N^2)의 시간복잡도 불가능
• w = (words의 길이)가 5,000 이므로 words의 O(w^2)의 시간복잡도 가능
• start와 end 인덱스를 설정하고 word의 길이만큼 슬라이싱한 리스트를 만들어 정렬하고 정렬된 words와 비교
• 정렬된 두 리스트가 같다면 answer 리스트에 start 추가

소스코드1

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        answer = []
        n = len(s)
        sorted_words = sorted(words)
        word_size = len(words[0])
        start = 0
        end = word_size * len(words)

        while end <= n:
            substring_words = [s[i:i + word_size] for i in range(start, end, word_size)]
            if sorted(substring_words) == sorted_words:
                answer.append(start)

            start += 1
            end += 1
            
        return answer

결과1

위와 같이 통과는 하지만 상당히 긴 실행시간을 소요하기 때문에 정렬이 아닌 다른 방법을 사용한 풀이를 생각해보자

접근방법2

• 접근방법1에서 시간복잡도가 높은 이유는 이미 찾은 단어들에 대해 window가 이동하면서 반복해서 검사하는 부분에 있다
• 이를 해결하기 위해서 word_lenght 만큼 슬라이싱 해가면서 word가 words에 포함되는지 검사한다
  • word가 words 안에 있는 경우
    • word_length 만큼 이동하면서 map에 계속해서 단어를 추가한다.
    • 추가한 word의 개수가 기존 words의 map에 있는 개수보다 많은 경우 가장 처음 단어를 제거하고 단어들의 개수가 같다면 해당 인덱스를 answer에 추가한다.
  • word가 words 안에 없는 경우
    • 현재 map과 단어개수를 초기화하고, left = j + word_length로 갱신 하여 이후에 등장하는 concatenated substring을 탐색한다

소스코드2

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        answer = []
        n = len(s)
        word_length = len(words[0])
        words_size = len(words)
        window_length = word_length * len(words)
        start = 0

        word_cnt = {}
        for word in words:
            if word in word_cnt:
                word_cnt[word] += 1
            else:
                word_cnt[word] = 1
                
        cur_word_cnt = {}
        for i in range(word_length):
            cur_cnt = 0
            left = i
            cur_word_cnt.clear()
            
            for j in range(i, n - word_length + 1, word_length):
                word = s[j:j + word_length]
                if word in word_cnt:
                    cur_word_cnt[word] = cur_word_cnt.get(word, 0) + 1
                    cur_cnt += 1

                    while cur_word_cnt[word] > word_cnt[word]:
                        left_word = s[left:left + word_length]
                        cur_word_cnt[left_word] -= 1
                        cur_cnt -= 1
                        left += word_length

                    if cur_cnt == words_size:
                        answer.append(left)
                else:
                    cur_word_cnt.clear()
                    cur_cnt = 0
                    left = j + word_length

        return answer