박종훈 알고리즘 블로그

(Leetcode) 139 - Word Break

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


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

dp 문제이다.

내가 푼 방식

from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)

        for i in range(1, len(s) + 1):
            temp = s[0:i]
            for word in wordDict:
                if len(temp) > len(word):
                    temp2 = temp[len(temp) - len(word): ]
                    if temp2 == word:
                        if dp[i - len(word)]:
                            dp[i] = True
                else:
                    if temp == word:
                        dp[i] = True

        return dp[-1]

S의 길이만큼 dp array를 만들었다. 길이를 늘려나가면서 각 길이마다 word가 break 되었는지 여부를 체크한다.

temp는 한 글자씩 늘려나가는데 사용되는 변수다. temp2는 temp에서 뒤에서부터 word의 길이만큼 빼서 생성하는 변수이다. 뒷부분에 단어 사전에 있는 단어가 있는지 확인한다. 만약 뒷부분이 단어 사전에 있는 단어라면, 그 단어의 앞부분의 dp 값을 확인한다. 왜냐면 최종적으로는 앞부분부터 단어 사전에 있는 단어로 꽉 차있는 형태여야 하기 때문이다.

예를들어 예시로 주어진 “catsandog”의 경우에는 다음과 같이 진행해볼 수 있을 것이다. (wordDict 도 동일하게 사용한다. [“cats”,”dog”,”sand”,”and”,”cat”])

  • dp[1] : c - False
  • dp[2] : ca - False
  • dp[3] : cat - True
  • dp[4] : cats - True
  • dp[5] : catsa - False
  • dp[6] : catsan - False
  • dp[7] : catsand - True

dp[7]의 경우 뒤를 확인해보면 sand 라는 단어를 가지고 있다. 앞에서 사용된 cat (dp[3]) 도 단어 사전에 있는 상태이므로 True가 된다.

하지만 이런식으로 좀 더 진행해보면 최종적으로 마지막은 False가 나온다.

시간복잡도

  • 이중 반복문 사용
    • 바깥쪽 반복문 : s의 길이 만큼 반복 (O(n))
    • 안쪽 반복문 : wordDict 리스트의 length 만큼 반복 (O(m))

O(n * m) 의 시간 복잡도를 가짐

공간복잡도

s의 길이만큼 dp 리스트를 생성함

O(n) 의 공간 복잡도를 가짐

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Leetcode , DP , word