[leetcode]139. Word Break

https://leetcode.com/problems/word-break/

리트코드 139번 문제는 사실 Dynamic Programming(DP) 로 이 문제를 풀어야한다는걸 알면 쉬운 문제입니다.

쉽게 가고 싶어서 Related Topics 를 잠깐 확인했고 DP 로 풀수 있는 문제라는걸 알게된 후에는 DP 적인 접근법으로 쉽게 알고리즘을 구현 할 수 있었습니다.

DP 는 작은 문제의 답을 이용해 큰 문제를 해결한다는 제귀법적 해결법과 메모이제이션을 조합한 알고리즘 접근법이다.

DP 설명을 위해 이전에 공유한 사다리 타기 문제를 공유합니다.

[동적계획법]사다리 올라가기

139번 문제의 DP 적 접근은 아래와 같습니다.

dp[i-len(word)] == True 이고 s[i:len(word)] == word 이라면 dp[i] = True 입니다.

사다리 타기와 약간 다른데, 현재 단어 이전까지가 조건을 만족한다면 현재 단어만큼만 확인해서 True 여부를 판단하면 됩니다.

class Solution(object):
    def wordBreak(self, s, wordDict):
        L = len(s)+1
        dp =[False]*L
        dp[0] = True
        for index in range(L):
            for word in wordDict:
                if index - len(word) >= 0 :
                    if dp[index-len(word)] == True and s[index-len(word) : index] == word :
                        dp[index] = True
                        break
        return dp[-1]

class Solution(object):

def wordBreak(self, s, wordDict):

L = len(s)+1

dp =[False]*L

dp[0] = True

for index in range(L):

for word in wordDict:

if index - len(word) >= 0 :

if dp[index-len(word)] == True and s[index-len(word) : index] == word :

dp[index] = True

break

return dp[-1]

DP 문제는 풀수 있는 작은 문제로 나누고 그 작은 문제를 활용해서 다음 문제를 푸는 방법으로 고민하면 방법을 찾아 나갈 수 있는것 같습니다.

다만, 이번 문제를 DP 로 접근해야한다는 걸 알아차리는게 쉽지 않았습니다( 처음에는 backtracking 으로 생각 했습니다.)

https://github.com/sok891111/leetcode/blob/main/WEEK26/139.%20Word%20Break.py