[2024] day 147. leetcode 140. Word Break II

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

2024년 5월 25일 (토)
Leetcode daily problem

140. Word Break II

https://leetcode.com/problems/word-break-ii/?envType=daily-question&envId=2024-05-25

Problem

Solution

backtracking

해당 문제는 백트래킹을 이용해 가능한 모든 문자열의 분할을 찾는 문제이다.
문자열을 첫번째 인덱스 부터 탐색해가면서 현재까지의 단어 조합을 나타내는 리스트 cur, 결과리스트 results, 현재 인덱스 idx로 idx 부터 문자열의 끝까지 가능한 모든 부분의 문자열을 추출하고 검사한다.
추출한 부분이 단어 사전에 있으면 단어 리스트 cur에 추가하고, 재귀적으로 현재 인덱스에서 +1부터 (end_idx) 부터 백트래킹을 호출한다.
재귀 호출이 끝나면 마지막으로 축가된 단어를 cur에서 제거해 백트래킹을 수행한다.

Code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        wordSet = set(wordDict)
        results = []
        self.backtracking(s, wordSet, [], results, 0)
        return results

    def backtracking(self, s, wordSet, cur, results, idx):
        if idx == len(s):
            results.append(' '.join(cur))
            return

        for end_idx in range(idx+1, len(s)+1):
            word = s[idx:end_idx]

            if word in wordSet:
                cur.append(word)
                self.backtracking(s, wordSet, cur, results, end_idx)
                cur.pop()

Complexicity

시간 복잡도

최악의 경우 모든 가능한 분할을 탐색해야 하고, 각 분할은 단어 사전에서 확인하므로 단어의 길이를 n, 단어사전의 크기를 m 이라고 한다면
문자열 s의 각 위치마다 분할을 시도하므로 O(2^n) 부분 문자열을 생성할 수 있다. 총 시간 복잡도는 O(2^n) 이다.

공간 복잡도

백트래킹의 최대 깊이는 n이므로 호출의 깊이도 O(n) 이다.
각 분할된 결과를 배열에 저장하고, 각 결과의 길이가 최악의 경우 O(2^n) 이게 된다. 단어사전을 단어 집합으로 변환하는 과정에서 O(m)이 필요하지만 m이 n보다 작다고 가정하면 총 공간 복잡도는 O(2^n) 이다.