[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (289일차)
[4코1파] 2023.01.13~ (281일차)
[4코3파] 2023.10.01 ~ (19일차)
Today :
2023.10.19 [289일차]
139. Word Break
https://leetcode.com/problems/word-break/
문제 설명
문자열 s와 문자열 wordDict 사전이 주어질때 문자열 s가 공백으로 구분된 하나 이상의 사전 단어 시퀀스로 분할될 수 있으면 True를 반환한다.
사전에 있는 단어는 여러 번 사용 될 수 있다!
문제 풀이 방법
이거 또한 brute force로 푼다면 o(n^2)으로 풀 수 있다.
wordDict에 담겨있는 문자들을 기준으로 트리를 그려가면서, 주어진 문자열과 비교해가면서 이동한다.
예를 들어 wordDict = ['neet', 'leet', 'code'] 가 있고 s = 'neetcode' 가 있다면
i =0 에서 시작해서 wordDict 에 있는 neet, leet, code (각 4글자) 에 해당하는 s이 있으면 i=4로 이동, 그 이후에 neet, leet, code후에 i=8까지 code가 있으므로 i = 8 로 문자열 끝까지 이상없이 이동했으므로 true 이다.
점화식은 dp[8] = True, dp[7] = False,
dp[6] = dp[5] = False, dp[4] = True, dp[3] = dp[2] = dp[1] = 1,
df[0] = dp[0 + len(w)] = True
내 코드
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[len(s)] = True
for i in range(len(s)-1, -1, -1):
for w in wordDict:
if (i+len(w)) <= len(s) and s[i:i+len(w)] == w:
dp[i] = dp[i+len(w)]
if dp[i]:
break
return dp[0]
증빙
여담
뭔말인지 모르겠는데 sequence model 하러가야해서 내일 다시봐야지
