Word Break
문자열 s와 단어 목록 wordDict가 주어집니다. s를 모두 wordDict에 있는 단어인 조각들로 나눌 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.
조각들은 순서를 유지하며, 함께 s의 모든 문자를 정확히 한 번씩 사용합니다. 하나의 단어는 여러 번 사용할 수 있으며, 모든 단어를 사용할 필요는 없습니다.
함수
- sstring
- 단어로 나눌 문자열
- wordDictstring-array
- 사용할 수 있는 단어들(각 단어는 원하는 만큼 사용 가능)
- 반환값boolean
- true는 s를 사전에 있는 단어들로 나눌 수 있는 경우이고, 그렇지 않으면 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하나만 남으므로 어떤 분할도 맞지 않습니다.
후속 질문
유효한 분할에 사용할 수 있는 최소 단어 수를 반환하고, s를 분할할 수 없으면 -1을 반환합니다. 표에서 무엇이 달라지며, 실행 시간도 달라지나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
어떤 단어든 잘라 낼 때 첫 부분은
s로 시작합니다. 단어를 고르고 나면 어떤 질문이 남을까요?어떤 인덱스부터 끝까지의 문자들을 잘라낼 수 있는지는 해당 인덱스에만 달려 있습니다. 이러한 질문은
n + 1개뿐이므로 각 답을 기억해 두세요. 특히false인 답을요.canEnd[i]가 처음i개의 문자를 분할할 수 있는지를 나타내도록 하고,canEnd[0] = true로 설정하세요. 그러면 어떤canEnd[start]가 true이고start부터end까지의 문자가 단어를 이루면canEnd[end]는 true입니다. 단어는 해시 집합에 저장하고, 가장 긴 단어보다 길지 않은 부분 문자열만 시도하세요.
풀이
한 번에 단어 하나씩 확정하는 방식은 실패하고, 모든 분할을 시도하는 것은 지수적으로 늘어납니다. 하지만 s의 나머지 부분을 분할할 수 있는지는 시작 위치에만 달려 있으므로, 질문은 n + 1개뿐입니다. 아래에서 n은 s의 길이이고, m은 단어의 개수이며, L은 가장 긴 단어의 길이입니다.
모든 위치에서 모든 단어를 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
첫 번째 조각은 s로 시작하는 단어여야 합니다. 그런 단어를 각각 시도하고, 남은 글자에 대해서도 같은 질문을 하세요. 남은 부분이 비어 있으면 모든 글자를 분할한 것입니다. 첫 번째 단어를 모두 시도한 다음 두 번째 단어를 모두 시도하면 유효한 분할을 놓칠 수 없습니다.
같은 나머지를 반복해서 확인합니다. a 299개 뒤에 b 하나가 있고, 단어가 a, aa부터 a 10개까지 있다면, b에 도달한 뒤 실패하는 방식으로 a를 블록으로 나누는 경우가 10^89가지 넘으며, 재귀는 그 경우를 모두 시도합니다.
알고리즘
canSplit(start)를 작성하세요.start부터 끝까지의 글자를 분할할 수 있나요?start가s의 길이와 같으면true를 반환합니다.s에start인덱스부터 포함된 각 단어에 대해,canSplit(start + its length)가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에만 달려 있으며, start는 n + 1개의 값을 가집니다. a의 예에서 인덱스 20의 나머지는 10개씩 두 블록을 지난 뒤, a 하나씩 스무 개를 지난 뒤, 그리고 셀 수 없이 많은 다른 방법으로 도달하며, 매번 false입니다. 각 start의 답을 한 번만 저장하고 재사용하세요.
메모에는 false 답도 저장해야 합니다. true가 나오면 전체 검색이 즉시 끝나므로, 반복되는 작업은 모두 실패하는 분기에서 발생합니다.
각 start는 모든 단어를 시도하며, 최대 L개의 글자를 비교합니다. 시간 복잡도는 O(n × m × L)이고, 글자 비교는 최대 6 × 10^6회이며, 공간 복잡도는 O(n)입니다.
알고리즘
- 인덱스마다 슬롯이 하나씩 있는 메모를 만들고, 각 슬롯을 아직 계산하지 않은 상태로 표시합니다.
canSplit(start)에서s의 끝에 도달하면true를 반환하고, 슬롯에 저장된 답이 있으면 그 답을 반환합니다.- 그렇지 않으면 단순 재귀 방식에서처럼 모든 단어를 시도하고,
false도 포함해 결과를 슬롯에 저장한 다음 반환합니다.
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]는 모두 이미 알고 있습니다.
단어들을 해시 집합에 넣습니다. 어떤 단어도 L보다 길지 않으므로 사전의 크기가 아무리 커도 end에서 끝나는 조각 중 일치할 수 있는 것은 L개뿐입니다. sunflowerseed에서 canEnd는 0, 3, 7, 9, 13에서 true입니다. 7에서 막다른 길에 도달해도 문제가 되지 않습니다.
n개의 위치 각각에서 최대 L개의 조각을 확인하고, 각 조각을 만들고 해싱하는 데 최대 L단계가 걸립니다. 따라서 O(n × L²)이며, 최대 1.2 × 10^5단계입니다. 여기에 집합을 위한 O(m × L)이 추가됩니다.
알고리즘
- 단어들을 해시 집합에 넣고 가장 긴 길이
L을 기록합니다. n + 1개의 항목이 있고 모두false인canEnd를 만들고,canEnd[0]을true로 설정합니다.- 각
end를 1부터n까지, 각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에서 막힙니다. - 메모에
true인 답만 저장하기. 반복 작업은false분기에서 발생하므로, a만 있는 예시는 여전히 지수 시간이 걸립니다. - 테이블의 항목을 하나 부족하게 만들기.
canEnd에는 접두사의 길이 0부터n까지를 위한 항목이n + 1개 필요합니다. s의 끝을 넘어 비교하기. 예를 들어 단어abc를 나머지ab와 비교하는 경우입니다. 먼저 길이를 확인하세요.- Lua와 R에서는 문자열 위치가 1부터 시작합니다. 문자
e에서 끝나는 길이k의 조각은e-k+1에서 시작합니다.
자주 묻는 질문3
Word Break의 시간 복잡도는 얼마인가요?
해시 집합을 사용하는 상향식 테이블은 O(m × L + n × L²)의 시간이 걸립니다. 여기서 n은 s의 길이이고, m은 단어의 개수이며, L은 가장 긴 단어의 길이입니다. 모든 위치에서 모든 단어를 비교하면 O(n × m × L)의 비용이 듭니다. 단순 재귀는 지수 시간이 걸립니다.
Word Break는 동적 프로그래밍 문제인가요, 아니면 그래프 문제인가요?
둘 다입니다. 동적 프로그래밍 관점에서 canEnd[i]는 처음 i개의 글자를 분할할 수 있는지를 나타냅니다. 그래프 관점에서는 각 인덱스가 노드이며, 그 사이의 글자들이 단어를 이루면 i에서 j로 가는 간선이 있습니다. 그리고 0에서 n에 도달할 수 있는지 확인합니다. 너비 우선 탐색은 테이블과 동일한 작업을 수행합니다.
참이나 거짓을 반환하는 대신 모든 문장을 어떻게 나열하나요?
백트래킹: 각 인덱스에서 들어맞는 모든 단어를 시도하고, 나머지 부분에 대해 재귀 호출한 다음, 각 인덱스의 문장 목록을 기억합니다. 먼저 참 또는 거짓 표를 실행하여 분할할 수 없는 문자열은 검색을 건너뛰게 합니다. 문장의 수는 기하급수적으로 늘어날 수 있으므로, 출력 크기가 실행 시간을 결정합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def wordBreak(s, wordDict):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
s = "sunflowerseed" wordDict = ["sun", "flow", "flower", "seed"]
예상 출력
true