LeetCode: 139. Word Break

단어를 분해하거나 단어에서 단어를 찾는 문제를 다룰 때 가장 먼저 해볼만한 접근은,

분해 대상 단어를 한글짜 단위로 확인해가면서 완전탐색하는 것이다.

아래는 완전 탐색 코드이다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.wordDict = set(wordDict)
        return self.dfs(s)
        
    def dfs(self, s):
        if not s:
            return True
        for i in range(1, len(s)+1):
            if s[:i] in self.wordDict:
                if self.dfs(s[i:]):
                    return True
        return False

 

제출해보면...?

타임 아웃이다.

생각해보면 dfs의 변수로 들어오는 s가 한번 계산된 경우, 추후 같은 s에 대해 dfs를 계산할 필요가 없다.

이점에 착안하면 아래처럼 코드를 변경할 수 있다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.wordDict = set(wordDict)
        self.dp = set()
        return self.dfs(s)
        
    def dfs(self, s):
        if not s:
            return True
        if s in self.dp:
            return False
        for i in range(1, len(s)+1):
            if s[:i] in self.wordDict:
                if self.dfs(s[i:]):
                    return True
        self.dp.add(s)
        return False