LeetCode의 Word Break 문제를 함께 풀어보도록 하겠습니다.
문제
문자열 s와 단어 사전 wordDict가 주어졌을 때, s가 wordDict 사전 내의 하나 이상의 단어로 분할될 수 있다면 참을 반환하라.
사전 내에서 같은 단어가 여러 번 사용되는 것이 허용된다는 점 주의하라.
예제
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: trueInput: 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"]결국 다시 맨 처음으로 거슬러 올라와보면 cats와 cat를 모두 시도해봤으므로 더 이상 선택할 수 있는 단어가 없는 것을 깨닫게 됩니다.
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"
TFFFTFFFTDP 배열의 마지막 인덱스에 있는 값이 우리가 반환해야 하는 최종 결과가 됩니다.
동일한 알고리즘을 두 번째 예제에 적용해보면 다음과 같은 모습으로 DP 배열이 저장이 될 것입니다.
0
"---------"
T01
"c--------"
TF012
"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-----"
TFFTT012345
"catsa----"
TFFTTF0123456
"catsan---"
TFFTTFF문자열 catsand은 단어 sand로 끝나므로, DP[7] = DP[7 - 4] = DP[3] = True
또는
문자열 catsand은 단어 and로 끝나므로, DP[7] = DP[7 - 3] = DP[4] = True
01234567
"catsand--"
TFFTTFFT012345678
"catsando-"
TFFTTFFTF0123456789
"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)가 되겠습니다.