Logo

Word Break

LeetCode의 Word Break 문제를 함께 풀어보도록 하겠습니다.

문제

문자열 s와 단어 사전 wordDict가 주어졌을 때, swordDict 사전 내의 하나 이상의 단어로 분할될 수 있다면 참을 반환하라.

사전 내에서 같은 단어가 여러 번 사용되는 것이 허용된다는 점 주의하라.

예제

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

풀이 1

문자열을 여러 단어로 분할할 수 있다는 말은 반대로 얘기하면 사전 내의 단어를 조합하여 문자열을 완성할 수 있다는 뜻도 되는데요.

먼저 첫 번째 예제가 왜 참을 반환해야하는지에 대해서 짚고 넘어가겠습니다.

우선 사전에 있는 단어 중에서 전체 문자열이 시작할 수 있는 단어가 있는지 확인해봅니다. 사전의 첫 번째 단어인 leet로 시작할 수 있겠네요.

s = "leetcode"
             ____
wordDict = ["leet", "code"]

이제 남아있는 문자열의 뒷 부분인 code만 확인하면 되겠죠? 사전의 두 번째 단어인 code가 딱 맞아 떨어지네요!

s = "----code"
                     ____
wordDict = ["leet", "code"]

문자열에서 더 이상 체크해야 할 부분이 남아있지 않으므로 우리는 참을 반환할 수 있다는 것을 알 수 있습니다.

s = "--------"

이번에는 두 번째 예제가 왜 거짓을 반환해야하는지도 생각해볼까요?

동일한 방식으로 사전에 있는 단어 중에서 전체 문자열이 시작할 수 있는 단어가 있는지 확인해봅니다. 사전 내의 첫 번째 단어인 cats로도 시작해도 되고, 마지막 단어인 cat으로 시작해도 되네요. 우선 cats으로 시도해보고, 나중에 안 되면 cat을 시도해보면 될 것 같습니다.

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

사전에 있는 단어 중에서 남은 문자열 andog이 시작할 수 있는 단어가 있는지 확인해봅니다. 사전 내의 네 번째 단어인 and로 시작할 수 있네요.

s = "----andog"
                                    ___
wordDict = ["cats", "dog", "sand", "and", "cat"]

다음 단계에서는 확인할 부분이 og로 줄어드는데 사전 내의 어떤 단어와도 일치하지 않습니다.

s = "-------og"
wordDict = ["cats", "dog", "sand", "and", "cat"]

이제 확인할 부분을 andog로 늘려서 and 말고 다른 단어로 시작할 수 있는지 보니 없네요.

s = "----andog"
wordDict = ["cats", "dog", "sand", "and", "cat"]

확인할 부분을 catsandog로 더 늘려서 cats 단어 대신에 사용할 수 있는 단어가 있는지 보겠습니다. 아까 전에 맨 처음에도 얘기했던 것처럼 이번에는 cat을 시도해 볼 차례입니다.

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

남아있는 문자열 sandog은 사전 내의 세 번째 단어인 sand로 시작할 수 있습니다.

s = "---sandog"
                            ____
wordDict = ["cats", "dog", "sand", "and", "cat"]

또 다시 확인할 부분이 og로 줄어드는데 사전 내의 어떤 단어와도 일치하지 않는다는 것을 알 수 있습니다.

s = "-------og"
wordDict = ["cats", "dog", "sand", "and", "cat"]

이제 확인할 부분을 sandog로 늘려서 sand 말고 다른 단어로 시작할 수 있는지 보니 없네요.

s = "---sandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]

결국 다시 맨 처음으로 거슬러 올라와보면 catscat를 모두 시도해봤으므로 더 이상 선택할 수 있는 단어가 없는 것을 깨닫게 됩니다.

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

이처럼 사전 내에 단어 중에서 문자열이 시작할 수 있는 단어가 있는지를 문자열의 맨 앞부터 확인할 부분을 점점 줄여가면서 재귀적으로 확인해나가다 보면 해결할 수 있는 있는데요. 이 재귀 알고리즘을 그대로 코드로 구현해보겠습니다.

from functools import cache

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @cache
        def dfs(start):
            if start == len(s):
                return True
            for word in wordDict:
                if s[start : start + len(word)] == word:
                    if dfs(start + len(word)):
                        return True
            return False

        return dfs(0)

파이썬의 @cache 데코레이터를 사용해서 메모이제이션(memoization) 기법을 적용했는데요. 이 방법에 익숙하지 않으신 분들은 사전을 사용하셔도 동일한 효과를 얻을 수 있습니다.

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

        def dfs(start):
            if start in memo:
                return memo[start]

            if start == len(s):
                memo[start] = True
                return True

            for word in wordDict:
                if s[start : start + len(word)] == word:
                    if dfs(start + len(word)):
                        memo[start] = True
                        return True

            memo[start] = False
            return False

        return dfs(0)

같은 알고리즘을 자바스크립트로도 한번 구현해보았습니다.

function wordBreak(s: string, wordDict: string[]): boolean {
  const memo = {};

  const dfs = (start) => {
    if (start in memo) return memo[start];

    if (start === s.length) {
      memo[start] = true;
      return true;
    }

    for (const word of wordDict) {
      if (s.substring(start, start + word.length) === word) {
        if (dfs(start + word.length)) {
          memo[start] = true;
          return true;
        }
      }
    }
    memo[start] = false;
    return false;
  };

  return dfs(0);
}

이 풀이의 시간 복잡도는 기본적으로 O(s^2^w)이 되지만 메모이제이션을 적용하면 중복 연산이 줄어들어 시간 복잡도를 O(s^2*w)로 대폭 향상시킬 수 있습니다. 반면에 재귀 알고리즘의 최대 메모리 사용량은 호출 스택의 깊이와 비례하므로 공간 복잡도는 O(s)가 되겠습니다.

풀이 2

위 재귀 풀이에서는 사전 내에 단어 중에서 문자열이 시작할 수 있는 단어가 있는지를 탐색했었는데요. 이번에는 반대로 사전 내에 단어 중에서 문자열이 끝날 수 있는 단어가 있는지 확인해보면 어떨까요?

이렇게 접근 방향을 전환하면 동적 계획법(Dynamic Programming)으로도 이 문제를 어렵지 않게 풀 수 있는데요. 기본 아이디어는 문자열의 길이를 0부터 1씩 늘려가면서 주어진 사전 내의 단어를 조합하여 해당 문자열을 완성할 수 있는지 없는지를 배열에 저장하는 것입니다. 그러면 짧은 문자열에서 구해놓은 결과를 긴 문자열에 대한 결과를 구할 때 활용할 수 있게 됩니다.

이 것을 DP를 배열이라 가정하고 수식으로 나타내볼까요?

길이가 s인 문자열의 길이가 길이가 w인 단어로 끝나지 않으면,

DP[s] = False

길이가 s인 문자열의 길이가 길이가 w인 단어로 끝난다면,

DP[s] = DP[s - w]

길이가 0인 문자열은 사전에 어떤 단어가 있는지와 무방하게 항상 만들 수 있으니 참이 되겠죠?

DP[0] = True

결과로 참을 얻어야하는 첫 번째 예제를 기준으로 생각해볼까요?

길이가 4인 문자열 leet는 길이가 4인 단어 leet로 끝나므로, 길이가 4 - 4 = 0인 문자열의 계산 결과를 활용할 수 있습니다. 즉, DP[0]이 참이니 DP[4]도 참이 되는 것이지요.

01234
"leet----"
TFFFT

길이가 8인 문자열 leetcode는 길이가 4인 단어 code로 끝나므로, 길이가 8 - 4 = 4인 문자열 leet의 계산 결과를 활용할 수 있습니다. 위에 구해 놓은 DP[4]가 참이니 DP[8]도 참이 되게 됩니다.

012345678
"leetcode"
TFFFTFFFT

DP 배열의 마지막 인덱스에 있는 값이 우리가 반환해야 하는 최종 결과가 됩니다.

동일한 알고리즘을 두 번째 예제에 적용해보면 다음과 같은 모습으로 DP 배열이 저장이 될 것입니다.

0
"---------"
T
01
"c--------"
TF
012
"ca-------"
TFF

문자열 cat은 단어 cat으로 끝나므로, DP[3] = DP[3 - 3] = DP[0] = True

0123
"cat------"
TFFT

문자열 cats은 단어 cats로 끝나므로, DP[4] = DP[4 - 4] = DP[0] = True

01234
"cats-----"
TFFTT
012345
"catsa----"
TFFTTF
0123456
"catsan---"
TFFTTFF

문자열 catsand은 단어 sand로 끝나므로, DP[7] = DP[7 - 4] = DP[3] = True

또는

문자열 catsand은 단어 and로 끝나므로, DP[7] = DP[7 - 3] = DP[4] = True

01234567
"catsand--"
TFFTTFFT
012345678
"catsando-"
TFFTTFFTF
0123456789
"catsandog"
TFFTTFFTFF

이렇게 두 번째 예제는 DP의 마지막이 거짓이 되므로 사전 내의 단어를 조합하여 문자열을 완성할 수 없다는 것을 알 수 있습니다.

이 DP 알고리즘을 코드로 한번 구현해 보겠습니다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True] + [False] * len(s)
        for n in range(1, len(s) + 1):
            for word in wordDict:
                if s[n - len(word) : n] == word:
                    dp[n] = dp[n - len(word)]
                if dp[n]:
                    break
        return dp[-1]

이 풀이의 시간 복잡도는 O(s^2*w)로써 메모이제이션을 적용한 재귀 풀이와 동일하게 됩니다. 공간 복잡도는 DP 배열의 길이가 입력 배열만큼 길어지므로 O(s)가 되겠습니다.