leetcode 139. Word Break 풀이

문제 : 주어진 문자열을 주어진 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/