Word Break
문자열 s와 단어 목록 wordDict가 주어집니다. s를 여러 조각으로 나누어 모든 조각이 wordDict의 단어가 되도록 할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.
조각은 순서를 유지하며, 모두 합쳐 s의 모든 문자를 정확히 한 번씩 사용합니다. 단어는 원하는 만큼 사용할 수 있으며, 모든 단어를 사용할 필요는 없습니다.
함수
- sstring
- 단어로 나눌 문자열
- wordDictstring-array
- 원하는 만큼 사용할 수 있는 단어
- 반환값boolean
- s를 사전 단어들로 분할할 수 있으면 true, 그렇지 않으면 false
제약 조건
1 ≤ s.length ≤ 3001 ≤ wordDict.length ≤ 10001 ≤ wordDict[i].length ≤ 20s와 모든 단어는 소문자 영어 문자만 포함합니다.-
wordDict의 단어는 모두 서로 다릅니다.
예제
- 입력
- s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
- 출력
- true
- 설명
sun,flower,seed로 나누세요.sun다음에flow를 취하면 남은er로 시작하는 단어가 없으므로 아무 데도 이어지지 않습니다. 따라서 조건에 맞는 첫 번째 단어가 항상 올바른 것은 아닙니다.
- 입력
- s = "bananaban"wordDict = ["ban", "ana"]
- 출력
- true
- 설명
ban+ana+ban는 문자열을 포함하며ban을 두 번 사용합니다. 이는 허용됩니다.
- 입력
- s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
- 출력
- false
- 설명
- 문자열은
pine+apple또는pineapple로 시작하며, 두 경우 모두tart가 남습니다. 그 자리에 들어갈 수 있는 유일한 단어는tar이고, 그러면t하나만 남으므로 어떤 방식으로 나누어도 맞지 않습니다.
제출 시 숨은 테스트 +21개
후속 질문
유효한 분할에 사용할 수 있는 최소 단어 수를 반환하거나, s를 분할할 수 없으면 -1을 반환하세요. 표에서 무엇이 바뀌며, 실행 시간은 달라지나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
어떤 분할이든 첫 번째 조각은
s로 시작하는 단어입니다. 이 단어를 고르면, 어떤 질문이 남을까요?어떤 인덱스부터 끝까지의 문자를 잘라낼 수 있는지는 그 인덱스에만 달려 있습니다. 이러한 질문은
n + 1개뿐이므로 각 답을 기억해 두세요. 특히false인 답을 기억하세요.canEnd[i]는 처음i개의 글자를 분할할 수 있는지를 나타내며,canEnd[0] = true입니다. 어떤canEnd[start]가 true이고start부터end까지의 글자가 단어를 이루면canEnd[end]는 true입니다. 단어들은 해시 집합에 저장하고, 가장 긴 단어보다 길지 않은 조각만 시도하세요.
풀이
그리디하게 분할하면 두 방향 모두 실패합니다. 가장 짧은 단어를 먼저 선택하면 sunflowerseed가 sun + flow로 분할되고, 가장 긴 단어를 먼저 선택하면 carpetal이 carpet으로 잘려 al이 남습니다. 따라서 선택지를 시도해 봐야 하며, 문자열은 지수적으로 많은 방식으로 분할될 수 있습니다. 이를 해결하는 핵심은 문자열의 나머지 부분을 분할할 수 있는지가 그 나머지 부분이 시작하는 위치에만 달려 있다는 점입니다. 따라서 서로 다른 질문은 n + 1개뿐입니다. 아래에서 n은 s의 길이이고, m은 단어의 개수이며, L은 가장 긴 단어의 길이입니다.
모든 위치에서 모든 단어를 시도하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
s를 왼쪽부터 읽습니다. 첫 번째 조각이 무엇이든, s가 그 단어로 시작해야 합니다. 그런 단어를 각각 시도하고, 각 단어에 대해 남은 글자들에 같은 질문을 합니다. 어떤 단어로든 끝까지 나눌 수 있다면 답은 true입니다. 그렇지 않다면 false입니다. 아무것도 남지 않으면 모든 글자를 나눈 것이므로 성공으로 간주합니다.
가능한 모든 첫 번째 단어를 시도한 다음, 가능한 모든 두 번째 단어를 시도하는 식으로 진행하므로 유효한 분할을 놓칠 수 없으며, 반환되는 모든 true에는 실제 분할이 있습니다.
같은 나머지 문자열을 반복해서 확인하기 때문에 느립니다. a를 299개 쓰고 뒤에 b를 하나 붙인 문자열을 생각해 보세요. 사용할 수 있는 단어는 a, aa 등 a가 열 개 있는 단어까지입니다. a들을 최대 열 개씩 묶어 나누는 모든 방법은 b까지 도달해 그 지점에서 실패하며, 그런 방법은 10^89개보다 많습니다. 답으로 false를 반환하기 전에 재귀는 그 방법을 전부 시도해야 합니다.
알고리즘
- 인덱스
start부터 끝까지의 글자를 단어들로 나눌 수 있는지 알려주는 도우미 함수canSplit(start)를 작성합니다. start가s의 길이와 같으면true를 반환합니다.- 각 단어에 대해
s에 인덱스start부터 해당 단어가 있는지 확인합니다. - 해당 단어가 있고
canSplit(start + length of the word)가true이면true를 반환합니다. - 어떤 단어도 맞지 않으면
false를 반환합니다. 정답은canSplit(0)입니다.
def wordBreak(s, wordDict):
def can_split(start):
# Can s[start:] be cut into dictionary words?
if start == len(s):
return True # nothing left to cut
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
return True
return False
return can_split(0)메모를 이용한 재귀
핵심 아이디어
나머지의 답은 시작 위치에 따라서만 달라지며, start는 n + 1개의 값만 가집니다. a의 예에서 인덱스 20에서 시작하는 나머지는 열 개씩 두 블록을 처리한 뒤에도, a 하나씩 스무 개를 처리한 뒤에도, 그리고 수많은 다른 방법으로도 도달할 수 있으며, 그 답은 매번 false입니다. 각 시작 위치에 대한 답을 처음 계산했을 때 저장하고, 이후에는 저장된 값을 읽어 오세요.
메모 슬롯에는 세 가지 상태가 필요합니다. 아직 계산하지 않음, true, false입니다. 중요한 것은 false라는 답입니다. true가 나오면 전체 탐색이 즉시 끝나므로, 일반 재귀가 반복하는 작업은 모두 실패하는 분기에서 발생합니다.
각 시작 위치는 한 번 계산되며 모든 단어를 시도하고, 최대 L개의 문자를 비교하므로 시간 복잡도는 O(n × m × L)입니다. 여기서는 최대 300 × 1000 × 20 = 6 × 10^6회의 문자 비교가 필요합니다. 메모와 호출 스택은 O(n)의 공간을 사용하며, 호출은 최대 300단계까지 중첩됩니다.
알고리즘
- 각 인덱스마다 하나의 슬롯이 있는 메모를 만들고, 각 슬롯을 아직 계산하지 않은 상태로 표시합니다.
canSplit(start)에서 문자열의 끝에 도달하면true를 반환하고,start의 슬롯에 저장된 답이 있으면 그 답을 반환합니다.- 그렇지 않으면 일반 재귀에서처럼
start에서 시작하는 모든 단어를 시도하고, 나머지 부분을 나눌 수 있는 첫 번째 단어에서 멈춥니다. - 결과를 슬롯에 저장합니다.
false도 저장한 다음 반환합니다. canSplit(0)을 반환합니다.
def wordBreak(s, wordDict):
memo = [None] * len(s) # memo[start]: answer for s[start:], None until worked out
def can_split(start):
if start == len(s):
return True
if memo[start] is not None:
return memo[start]
result = False
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
result = True
break
memo[start] = result
return result
return can_split(0)해시 집합을 사용한 접두사의 상향식 처리
핵심 아이디어
방향을 바꾸어 접두사에 대해 살펴봅시다. canEnd[i]는 처음 i개의 글자를 단어들로 나눌 수 있는지를 나타냅니다. 빈 접두사는 단어가 필요하지 않으므로 canEnd[0]은 true입니다. 처음 end개의 글자를 나눌 수 있는 경우는 마지막 조각, 즉 start부터 end까지의 글자가 단어이고 그 앞의 글자들도 나눌 수 있을 때입니다. 다시 말해 canEnd[start]가 true여야 합니다. 표를 왼쪽에서 오른쪽으로 채우면 필요한 canEnd[start]는 이미 알고 있습니다.
각 위치에서 m개의 단어를 모두 비교하는 대신, 단어들을 해시 집합에 넣고 가능한 마지막 조각을 조회합니다. 어떤 단어도 L보다 길지 않으므로 end에서 끝나는 조각 중 일치할 수 있는 것은 최대 L개뿐입니다. sunflowerseed에서 canEnd는 0, 3(sun), 7(flow), 9(flower), 13(위치 9 다음의 seed)에서 true가 되므로 답은 true입니다. 위치 7에서는 더 나아갈 수 없는데, er로 시작하는 단어가 없기 때문입니다. 표는 이를 신경 쓰지 않습니다.
n개의 위치가 있고, 각 위치에서 최대 L개의 조각을 조회하며, 조각을 만들고 해싱하는 데 최대 L단계가 걸립니다. 따라서 사전의 크기가 아무리 커도 최대 300 × 20 × 20 = 1.2 × 10^5 글자 단계, 즉 O(n × L²)입니다. 집합을 만들 때는 각 단어를 한 번씩 읽으므로 O(m × L)이고, 전체 시간 복잡도는 O(m × L + n × L²)입니다. 집합에는 단어들이 저장되므로 글자 수 기준으로 O(m × L)의 공간을 사용하고, 표에는 n + 1개의 플래그가 저장됩니다. 재귀는 없습니다.
알고리즘
- 각 단어를 해시 집합에 넣고, 가장 긴 단어의 길이
L을 기록합니다. n + 1개의 항목을 가진canEnd를 만들고, 모두false로 설정한 다음canEnd[0]을true로 설정합니다.end를 1부터n까지 순회하며, 각end에 대해length를 1부터min(L, end)까지 시도합니다.canEnd[end-length]가true이고end에서 끝나는 해당 길이의 부분 문자열이 집합에 있으면,canEnd[end]를true로 설정하고 길이 시도를 중단합니다.canEnd[n]을 반환합니다.
def wordBreak(s, wordDict):
words = set(wordDict)
longest = max(len(word) for word in wordDict)
n = len(s)
# can_end[i]: the first i letters split into dictionary words
can_end = [False] * (n + 1)
can_end[0] = True # the empty prefix needs no words
for end in range(1, n + 1):
# The last word is s[end-length:end], and no word is longer than longest.
for length in range(1, min(longest, end) + 1):
if can_end[end - length] and s[end - length:end] in words:
can_end[end] = True
break
return can_end[n]
함정과 경계 사례
대부분의 오답은 너무 일찍 한 가지 분할 방법을 선택하거나, 실패를 기억하지 않는 탐색에서 비롯됩니다.
- 탐욕적으로 분할하기. 가장 긴 단어를 먼저 선택하면
carpetal을carpet으로 나누고al이 남지만,car+petal은 가능합니다. 가장 짧은 단어를 먼저 선택하면sunflowerseed에서 실패합니다. s의 모든 문자가 어떤 단어에든 등장하는지만 확인하기. 단어가aaaa와aa라면 각 조각의 길이는 모두 짝수이므로, 글자가 일곱 개인aaaaaaa는 분할할 수 없습니다.true인 답만 메모에 저장하기.true이면 어차피 탐색이 끝납니다. 반복되는 작업은false인 분기에서 일어나므로, 그런 결과를 저장하지 않는 메모는 여전히 지수 시간이 걸립니다.- 테이블의 항목 수를 하나 적게 만들기.
canEnd[i]는 처음i개의 글자에 관한 것이며, 0과n이 모두 유효하므로 항목이n + 1개 필요합니다. - 남은 부분보다 단어가 더 길 때, 예를 들어
ab에 단어abc를 대조할 때s의 끝을 넘어 비교하기. 글자를 비교하기 전에 길이를 확인하세요. - Lua와 R에서는 문자열 위치가 1부터 시작합니다. 글자
e에서 끝나는 길이k의 조각은 글자e-k+1에서 시작합니다.
자주 묻는 질문4
Word Break의 시간 복잡도는 얼마인가요?
해시 집합을 사용하는 상향식 테이블 방식은 O(m × L + n × L²) 시간에 실행됩니다. 여기서 n은 s의 길이, m은 단어의 개수, L은 가장 긴 단어의 길이입니다. 집합을 만들 때 각 단어를 한 번씩 읽으며, n개의 각 위치에서 길이가 최대 L인 조각을 최대 L개 조회합니다. 대신 각 위치에서 모든 단어를 비교하면 O(n × m × L)입니다. 메모이제이션이 없는 단순 재귀는 지수 시간이 걸립니다.
Word Break에서 그리디 접근법은 왜 실패할까요?
탐욕적 규칙은 한 단어를 선택하고 다시 고려하지 않습니다. 가장 긴 단어를 먼저 선택하면 carpetal이 carpet과 al로 나뉘지만, car + petal은 제대로 작동합니다. 가장 짧은 단어를 먼저 선택하면 sunflowerseed가 sun + flow로 나뉘고 erseed에서 막힙니다. 동적 프로그래밍은 어떤 분할로든 도달할 수 있는 모든 위치를 유지하므로 올바른 위치를 놓치지 않습니다.
Word Break는 동적 프로그래밍 문제인가요, 아니면 그래프 문제인가요?
두 관점 모두 유효합니다. 동적 프로그래밍으로 보면 canEnd[i]는 처음 i개의 문자를 나눌 수 있는지를 나타내며, 더 작은 접두사들을 바탕으로 만들어집니다. 그래프로 보면 모든 인덱스가 노드이고, i부터 j까지의 문자들이 단어를 이룰 때 i에서 j로 향하는 간선이 있으며, 노드 0에서 노드 n에 도달할 수 있는지 묻습니다. 방문 집합을 사용하는 너비 우선 탐색은 테이블과 같은 작업을 합니다.
참 또는 거짓을 반환하는 대신 모든 문장을 어떻게 나열하나요?
백트래킹을 사용하세요. 각 인덱스에서 맞는 모든 단어를 시도하고, 나머지 부분에 대해 재귀 호출하면서 문장을 만들어 나가세요. 각 인덱스에 대한 문장 목록을 기억해 나머지 부분을 한 번만 해결하도록 하세요. 먼저 참/거짓 표를 실행하여 분할할 수 없는 문자열은 탐색을 건너뛰게 하세요. 문장 수가 지수적으로 증가할 수 있으므로 출력 크기가 실행 시간을 결정합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def wordBreak(s, wordDict):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
s = "sunflowerseed" wordDict = ["sun", "flow", "flower", "seed"]
기대값
true