139. Word Break

[zeikar]

Problem link

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

Problem Summary

스트링과 단어 리스트가 주어질 때 단어들을 이어붙여 스트링을 만들수 있는지 판단하는 문제.

Solution

간단한 DP 문제이다.

현재까지 인덱스를 dp로 저장해두고 단어를 이어붙일 수 있다면 계속 이어붙여주면 된다.
점화식을 세우자면

dp[i] =  dp[i - words[j]] (가능한 모든 단어들)

이런 느낌이 된다.

s의 길이를 N, 단어의 개수 M, 각 단어 길이를 W라 하면 시간복잡도는 O(N M W)가 된다. 단어를 비교할 때 W가 소요됨.

Source Code

from functools import cache
from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        @cache
        def solve(idx: int):
            if idx == len(s):
                return True
            if idx > len(s):
                return False

            ret = False
            for word in wordDict:
                if s[idx:idx + len(word)] == word:
                    ret |= solve(idx + len(word))

            return ret

        return solve(0)