[leetcode 매일 풀기] 30 substring with concatenation of all words

오늘 리뷰할 문제는 30번 substring with concatenation of all words이다.

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

Substring with Concatenation of All Words - LeetCode

 

주어진 문자열 s와, 같은길이의 단어들의 목록(words)가 주어졌을 때, s의 substring중 words안의 단어의 재배치로 얻을 수 있는 substring의 시작위치와 종료위치를 찾는 문제이다.

 

같은길이의 단어들의 목록이므로, s의 substring도 시작위치가 정해지면 같은 길이로 words의 갯수만큼 만들면 해당 substring이 가지고 있는 단어의 목록을 얻을 수 있고. 해당 단어의 목록과 words를 비교해서 결과를 찾으면 된다.

 

추가로 비교를 해야할 때는, substring의 시작단어와, 다음단어만 가지고 다음 substring의 단어의 목록을 구할 수 있다.

그리고 단어의 길이만큼 시작 index를 달리 가져가면서 iteration을 돌리면 모든 substring에 대해서 확인을 할 수 있다.

 

Dictionary로 직접 구현한 코드

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        words_map_count = dict()
        for word in words:
            if word in words_map_count:
                words_map_count[word] += 1
            else:
                words_map_count[word] = 1

        word_count = len(words)
        word_len = len(words[0])
        results = []

        for i in range(word_len):
            # initialize first sequence
            start_index = i
            end_index = i + word_len * word_count
            if end_index > len(s):
                break
            match_map_count = dict()
            for j in range(word_count):
                word = s[start_index + j * word_len : start_index + (j + 1) * word_len]
                if word in match_map_count:
                    match_map_count[word] += 1
                else:
                    match_map_count[word] = 1

            if match_map_count == words_map_count:
                results.append(start_index)
            start_index = start_index + word_len
            end_index = end_index + word_len

            while end_index <= len(s):
                before_word = s[start_index - word_len : start_index]
                after_word = s[end_index - word_len : end_index]
                if before_word in match_map_count:
                    match_map_count[before_word] -= 1
                    if match_map_count[before_word] == 0:
                        del match_map_count[before_word]
                if after_word in match_map_count:
                    match_map_count[after_word] += 1
                else:
                    match_map_count[after_word] = 1

                if match_map_count == words_map_count:
                    results.append(start_index)
                start_index = start_index + word_len
                end_index = end_index + word_len

        return results

 

속도는 잘 나오는데, 메모리가 조금 많이 잡아먹는 느낌이 있다.

 

 

다른 사람의 코드를 비교했을 때, collection.Counter를 사용하니 코드가 조금 더 깔끔해셔서 반영한 것은 다음과 같다.

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        words_map_count = dict()
        for word in words:
            if word in words_map_count:
                words_map_count[word] += 1
            else:
                words_map_count[word] = 1

        word_count = len(words)
        word_len = len(words[0])
        results = []

        for i in range(word_len):
            # initialize first sequence
            start_index = i
            end_index = i + word_len * word_count
            if end_index > len(s):
                break
            match_map_count = dict()
            for j in range(word_count):
                word = s[start_index + j * word_len : start_index + (j + 1) * word_len]
                if word in match_map_count:
                    match_map_count[word] += 1
                else:
                    match_map_count[word] = 1

            if match_map_count == words_map_count:
                results.append(start_index)
            start_index = start_index + word_len
            end_index = end_index + word_len

            while end_index <= len(s):
                before_word = s[start_index - word_len : start_index]
                after_word = s[end_index - word_len : end_index]
                if before_word in match_map_count:
                    match_map_count[before_word] -= 1
                    if match_map_count[before_word] == 0:
                        del match_map_count[before_word]
                if after_word in match_map_count:
                    match_map_count[after_word] += 1
                else:
                    match_map_count[after_word] = 1

                if match_map_count == words_map_count:
                    results.append(start_index)
                start_index = start_index + word_len
                end_index = end_index + word_len

        return results

 

속도가 살짝 느려지는데, 조금 더 이해하기 편한 것 같아서 좋다.

 

다른 사람들의 코드를 봤을 때 iteration을 돌 때 중간 결과물을 재사용하지 않고, 모든 substring에 대해서 매번 word의 목록을 계산해서 비교하는 경우가 있더라.

time complexity를 계산해보면 (len s = S, len words: N, len or word: M)
모든 substring에 대해서 매번 word 목록 계산해서 비교하는 경우
Counter 만드는데 = O(N)
Check Substring 하는데 = O(N)
Check Substring 횟수 = O(S) = O(N)*O(S)

내 Timecomplexity를 계산해보자
Counter 만드는데 = O(N)
for loop 한번에
 첫 Substring 만드는데 = O(N)
 비교하는데 드는 비용 = O(M)
 비교 횟수 = O(S/M)
for loop 횟수는 O(M)
O(N) + O(M) * (O(N) + O(M) * O(S/M)) = O(N) + O(MN) + O(SM) = O(M(S+N)) 이다.
내게 조금 더 나은 것을 볼 수 있다.