[2024] day 160. leetcode 648. Replace Words

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 7일 (금)
Leetcode daily problem

648. Replace Words

https://leetcode.com/problems/replace-words/?envType=daily-question&envId=2024-06-07

Problem

영어에는 "root"라는 개념이 있는데, "root" 뒤에는 다른 단어가 따라와서 또 다른 긴 단어를 형성할 수 있다. 이 단어를 파생어라고 한다. 예를 들어, 어근 "help" 뒤에 "ful"이라는 단어가 오면 "helpful"이라는 파생어를 만들 수 있다.

많은 어근으로 구성된 사전과 공백으로 구분된 단어로 구성된 문장이 주어지면 문장의 모든 파생어를 문장을 구성하는 어근으로 바꾼다. 파생어가 둘 이상의 근으로 대체될 수 있는 경우 이를 가장 짧은 길이를 갖는 root 으로 대체한다. 교체 후 문장을 반환한다.

Code

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        
        wordDict = set(dictionary)
        wordArray = sentence.split(' ')
        
        def get_word(word, wordDict):
            for i in range(len(word)):
                tmp = word[0:i]
                if tmp in wordDict:
                    return tmp
            return word
        
        for i in range(len(wordArray)):
            wordArray[i] = get_word(wordArray[i], wordDict)
            
        return ' '.join(wordArray)

Complexicity

시간 복잡도

주어진 단어 딕셔너리를 집합(set)으로 변환하는 데 걸리는 시간은 단어가 m개라고 했을 때 O(m) 이 소요됐다.
길이 n (문장의 총 문자 수)인 문장을 공백으로 나누는 데 걸리는 시간은 O(n) 이다.

반복문에서 길이 k인 단어에 대해, 모든 접두사를 집합에서 확인하는데 걸리는 시간은 최악의 경우 O(k^2)이다.
여기서 접두사 슬라이스 연산이 O(i)이고, 집합의 조회 시간은 평균적으로 O(1)이므로 이 함수는 최악의 경우
O(k^2)이 시간이 걸린다.

시간 복잡도: 전체 알고리즘의 시간 복잡도는
O(n⋅L^2+m) 이다. n은 문장의 총 문자 수, L은 단어의 평균 길이, m은 사전(dictionary) 단어의 수 이다.

공간 복잡도
집합에 단어들을 저장하는 데 필요한 공간은 O(m) 이 필요하다.단어들을 저장하는 배열의 공간 복잡도는 O(n) 이 필요하다.
tmp는 매번 새로운 접두사를 저장하며, 각 호출 시 최대
O(k)공간을 사용한다. 함수 자체는 추가적으로 O(1) 공간을 필요로 한다.

전체 알고리즘의 공간 복잡도는 O(n+m)이다.
여기서 n은 문장의 총 문자 수, m은 사전 단어의 수 이다.