이 문제는 **Dynamic Programming (동적 프로그래밍)**을 사용해서 효율적으로 풀 수 있습니다.
"Word Break" 문제라고 불리는 전형적인 문제 중 하나입니다. 다음은 문제를 푸는 방법에 대한 자세한 설명입니다.
문제 풀이 방법
- 아이디어
- 문자열 s를 특정 위치에서 쪼개서, 각 부분 문자열이 wordDict에 있는 단어로 구성되어 있는지 확인합니다.
- dp[i]를 정의: s[0:i]까지의 부분 문자열을 wordDict의 단어들로 분해할 수 있는지를 나타내는 boolean 값.
- 기본 상태: dp[0] = True (빈 문자열은 항상 분해 가능).
- 점화식
- dp[i] = True가 되려면, 아래 조건이 충족되어야 합니다:
- 어떤 j(0 ≤ j < i)에 대해, dp[j] == True이고 s[j:i]가 wordDict에 포함되어 있어야 합니다.
- 즉, dp[i] = dp[j] and s[j:i] in wordDict 조건을 만족하는 j가 존재하면 됩니다.
- dp[i] = True가 되려면, 아래 조건이 충족되어야 합니다:
- 구현 순서
- 문자열 s의 길이를 기준으로, dp 배열을 채워갑니다.
- 매 위치에서 가능한 모든 분할(j)을 확인하여 dp 값을 갱신합니다.
- 복잡도
- 시간 복잡도: O(n^2), 여기서 n은 문자열 s의 길이.
- 공간 복잡도: O(n)(dp 배열 사용).
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# wordDict를 set으로 변환해 탐색 속도를 높임 (O(1)로 검색 가능)
word_set = set(wordDict)
# 문자열 s의 길이를 n에 저장
n = len(s)
# dp 배열 초기화: 길이 n+1, 모두 False로 설정
# dp[i]는 s[0:i]까지의 문자열이 wordDict로 분해 가능한지를 나타냄
dp = [False] * (n + 1)
# dp[0] = True: 빈 문자열은 항상 분해 가능하므로 True로 설정
dp[0] = True
# 문자열의 길이 1부터 n까지 순회하며 dp 배열 채우기
for i in range(1, n + 1):
# 현재 i를 기준으로 이전 문자열의 모든 분할점 j를 순회
for j in range(i):
# dp[j]가 True이고, s[j:i]가 wordDict에 존재한다면
# s[0:j]까지 분해 가능하며 s[j:i]가 단어 사전에 포함됨을 의미
if dp[j] and s[j:i] in word_set:
# dp[i]를 True로 갱신: s[0:i]까지의 문자열이 분해 가능하다는 뜻
dp[i] = True
# 하나라도 True가 확인되면 더 탐색할 필요가 없으므로 루프 종료
break
# dp[n]의 값을 반환: 문자열 s 전체가 분해 가능한지 여부
return dp[n]
기본 아이디어
- dp[i]는 s[0:i] (문자열 s의 처음부터 i까지의 부분 문자열)이 wordDict의 단어들로 쪼개질 수 있는지를 나타냅니다.
- dp[0] = True로 시작합니다. 빈 문자열은 항상 분해 가능하다는 뜻입니다.
다른 예제
요약
- j 루프의 역할: 현재 위치 i를 기준으로 모든 이전 위치 j를 확인하여, s[j:i]가 word_set에 있는지 확인합니다.
- dp[j] == True: j 이전까지의 문자열은 이미 분해 가능하다는 뜻입니다.
- s[j:i] in word_set: j부터 i까지의 부분 문자열이 단어 사전에 포함되어 있는지 확인합니다.
- 이를 통해 현재 i까지의 문자열(s[0:i])이 분해 가능한지 판별합니다.
방법 2: DFS + 백트래킹
아이디어
- 문자열을 재귀적으로 쪼개어 wordDict에 포함된 단어로 나눌 수 있는지 확인합니다.
- 방문한 인덱스를 메모이제이션(cache)하여 중복 연산을 방지합니다.
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict) # 단어를 빠르게 검색하기 위해 set 사용
n = len(s)
cache = {} # 메모이제이션을 위한 딕셔너리
def dfs(start):
# 문자열의 끝까지 도달하면 True 반환
if start == n:
return True
# 이미 계산한 위치라면 결과 반환
if start in cache:
return cache[start]
# 현재 위치에서 가능한 모든 끝 위치를 탐색
for end in range(start + 1, n + 1):
# s[start:end]가 wordDict에 있고, 나머지 부분도 분해 가능하다면 True
if s[start:end] in word_set and dfs(end):
cache[start] = True
return True
# 어떤 분할도 불가능하면 False 저장
cache[start] = False
return False
return dfs(0)
시간 복잡도
- 최악의 경우 O(n^2): 모든 가능한 부분 문자열을 탐색.
- 하지만 메모이제이션으로 중복 연산을 줄이므로 효율적.
방법 3: BFS (Breadth-First Search)
아이디어
- 그래프 탐색처럼 s의 각 위치를 노드로 보고, 가능한 모든 부분 문자열을 큐에 추가하여 탐색합니다.
- 방문한 노드는 다시 탐색하지 않도록 visited 집합을 사용합니다.
from typing import List
from collections import deque
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict) # 단어를 빠르게 검색하기 위해 set 사용
n = len(s)
queue = deque([0]) # 시작 위치를 큐에 추가
visited = set() # 방문한 위치를 저장
while queue:
start = queue.popleft()
# 이미 방문한 위치는 건너뛰기
if start in visited:
continue
# start 위치에서 끝 위치를 탐색
for end in range(start + 1, n + 1):
# s[start:end]가 wordDict에 있다면
if s[start:end] in word_set:
# 문자열의 끝에 도달하면 True 반환
if end == n:
return True
# 끝 위치를 큐에 추가
queue.append(end)
# 현재 위치를 방문 처리
visited.add(start)
# 가능한 분해를 찾지 못한 경우 False 반환
return False
시간 복잡도
- 최악의 경우 O(n^2): 모든 부분 문자열을 탐색.
- 하지만 visited를 사용하여 중복 탐색을 방지.
https://youtu.be/Sx9NNgInc3A?si=w-SzGf0ygxUGjpf0
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# 결정 트리: decision tree
# 캐쉬
# DP
"""
# bottom up 으로..
# 그래서 s 문자열의 끝에서부터 ..검색
# wordDict = ["neet", "leet","code"]
# s = neetcode 라면
# 012345678
# dp[시작지점]
# dp[8] 은.. 종료 .. 잘 찾았다면. 잘 종료했을테니 dp[8] = True, 기본 세팅
# dp[7]: 문자열 'e' 이것은 wordDict에 없고,
wordDict의 어떤 문자열의 길이만큼의 단어도 아님
따라서, dp[7] = False
# dp[6]: 문자열 'de' 이것은 wordDict에 없고,
wordDict의 어떤 문자열의 길이만큼의 단어도 아님
따라서, dp[6] = False
# dp[5]: 문자열 'ode' 이것은 wordDict에 없고,
wordDict의 어떤 문자열의 길이만큼의 단어도 아님
따라서, dp[5] = False
# dp[4]: 문자열 'code' 이것은 wordDict에 있어서 dp[4] = True
# dp[3]: 문자열 t 부터 시작하는 단어..
이것은 wordDict의 어떤 문자열의 길이만큼의 단어로 하니,
tcod 인데, wordDict 에 없음
따라서, dp[3] = False
# dp[2]: 문자열 e 부터 시작하는 단어..
이것은 wordDict의 어떤 문자열의 길이만큼의 단어로 하니,
etco 인데, wordDict 에 없음
따라서, dp[2] = False
# dp[1]: 문자열 e 부터 시작하는 단어..
이것은 wordDict의 어떤 문자열의 길이만큼의 단어로 하니,
eetc 인데, wordDict 에 없음
따라서, dp[1] = False
# dp[0]: 문자열 n 부터 시작하는 단어..
이것은 wordDict의 어떤 문자열의 길이만큼의 단어로 하니,
neet 인데, wordDict 에 있음
따라서, dp[0] = True
# 규칙: dp[0] = d[0 + len(w)] = True
"""
# dp 배열 초기화, dp[i]는 s[i:] 문자열이 wordDict로 분해 가능한지 나타냄
dp = [False] * (len(s) + 1)
# 문자열의 끝은 항상 True, 빈 문자열은 분해 가능
dp[len(s)] = True
# 문자열의 끝에서부터 시작하여 dp 배열을 채움
for i in range(len(s) - 1, -1, -1): # i를 len(s)-1에서 0까지 순회
for w in wordDict: # wordDict의 각 단어를 순회
# i에서 시작해 w의 길이만큼 자른 문자열이 wordDict에 있는지 확인
if (i + len(w)) <= len(s) and s[i: i + len(w)] == w:
# dp[i]를 업데이트: dp[i]는 dp[i + len(w)]의 값으로 설정
dp[i] = dp[i + len(w)]
# dp[i]가 True면 더 이상 확인할 필요 없음
if dp[i]:
break
# dp[0] 반환: s 전체 문자열이 wordDict로 분해 가능한지 나타냄
return dp[0]
https://youtu.be/-qMVFoVyTqY?si=ZkQmhyRaxq1SvGGl
'LeetCode > DP심화' 카테고리의 다른 글
| 120. Triangle (0) | 2024.12.30 |
|---|---|
| 322. Coin Change (0) | 2024.12.29 |
| 746. Min Cost Climbing Stairs ★ (0) | 2024.11.23 |
| 1137. N-th Tribonacci Number (1) | 2024.11.22 |
| 714. Best Time to Buy and Sell Stock with Transaction Fee (2) | 2024.11.08 |