(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) 의 공간 복잡도를 가짐

자바로 다시 풀어보기 (240709)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                if (i >= word.length()) {
                    int start = i - word.length();
                    if (dp[start] && s.startsWith(word, start)) {
                        dp[i] = true;
                    }
                }
            }
        }

        return dp[s.length()];
    }
}

TC, SC

s의 길이를 n 이라 하고, wordDict의 크기를 m 이라고 할 때, 시간복잡도는 O(n * m) 공간복잡도는 O(n) 이다.