[LeetCode] Word Break 풀이 - (python 파이썬)

사용 언어: Python 파이썬

문제: https://leetcode.com/problems/word-break/

Word Break - LeetCode

이 문제는 Dynamic Programming으로 풀었다.

 

Dynamic Programming이란?

Dynamic Programming(동적 계획법)은 주어진 문제를 잘게 나누어서 하위 문제들을 푼 후, 각 답을 이용하여 주어진 문제를 푸는 방식이다. DP를 풀 때 생각해야하는 것은 딱 하나다. 바로 '점화식'이다. 점화식만 세우면 문제 풀이는 끝났다.

 

주어진 문제를 읽어보자.

Input

- non-empty 문자열 s

- non-empty 단어들을 담고있는 딕셔너리 wordDict (중복된 단어는 주어지지 않는다.)

 

Output

wordDict의 단어를 사용하여 (하나의 단어 중복 사용 가능) 주어진 s를 만들 수 있으면 True를 반환, 없으면 False 반환하면 된다.

 

주어진 예시는 다음과 같다.

Input: s = "leetcode", wordDict = ["leet", "code"]

Output: true

 

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output: false

 

s를 처음부터 순회하면서, wordDict에 있는 단어이면 마지막 위치의 index를 True로 바꿔준다. 그래서 s의 마지막 인덱스 값을 출력하는 방식으로 접근했다.

 

leetcode라는 단어를 예시로 생각해보자.

dp[0] = True

dp[1] = False // wordDict에 "l"이라는 단어는 없다.

dp[2] = False // wordDict에 "le"라는 단어는 없다.

dp[3] = False // wordDict에 "lee"라는 단어는 없다.

dp[4] = True // wordDict에 "leet"이라는 단어가 있다.

dp[5] = False // wordDict에 "c"라는 단어는 없다.

dp[6] = False // wordDict에 "co"라는 단어는 없다.

dp[7] = False // wordDict에 "cod"라는 단어는 없다.

dp[8] = True // wordDict에 "code"라는 단어가 있다.

 

구하고자 하는 점화식은 다음과 같다.

dp[i] = wordDict의 단어들로 s(0:i)의 부분 문자열을 만들 수 있는지!

dp[n] = 문자열 s의 j번째 인덱스부터 n번째 인덱스까지의 부분 문자열이 wordDict에 있으면 True, 이때 j는 dp[j]의 값이 True여야한다.

 

이를 코드로 옮겨보자

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        
        dp = [i==0 for i in range(n+1)]
        
        for i in range(1, n+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break

        return dp[-1]