문제 : 주어진 문자열을 주어진 wordDict의 문자열로 완전히 나눌 수 있는지 여부를 반환하라.
Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".
Follow up :
아이디어 : find를 통해 wordDict와 일치하는 문자열의 시작 index를 찾은 후 그것을 기준으로 문자열을 나누어서 재귀로 탐색하려 했다. 하지만 이 경우에는 제대로 된 반환 값을 전달하기 힘든 문제와 시간 복잡도의 증가로 인해 문제를 풀지 못했다.
코드 :
다른 사람이 짠 코드
def wordBreak(self, s, wordDict):
n = len(s)
dp = [False for i in range(n+1)]//*Changed*
dp[0] = True
for i in range(1,n+1):
for w in wordDict:
if dp[i-len(w)] and s[i-len(w):i]==w://*Changed*
dp[i]=True
return dp[-1]
학습 포인트 : 다른 사람이 짠 코드를 보면 false로 이루어진 dp array를 생성하여 index만을 비교하여 문제를 풀었다. 이 부분은 조금 더 생각해봐야 할 것이다.
출처 : leetcode.com/problems/word-break/
'프로그래밍' 카테고리의 다른 글
leetcode 63. Unique Paths II 풀이 (0) | 2021.05.03 |
---|---|
leetcode 733. Flood Fill 풀이 (0) | 2021.04.27 |
leetcode 62. Unique Paths 풀이 (0) | 2021.04.23 |
leecode 238. Product of Array Except Self 풀이 (0) | 2021.04.23 |
leecode 22. Generate Parentheses 풀이 (0) | 2021.04.23 |