Leetcode - Word Break

Leetcode Word Break에 대한 복기이다.

Naive Approach

기존에 생각한 방식은 루프가 돌면서, start라는 변수부터 i-1까지의 substring이 wordDict에 존재하는지 확인하고, 존재하면 start를 i로 해서 맨 마지막에 start이 s의 길이 n이면 True 아니면 False를 반환하는 프로그램을 구상했다.

start = 0
for i in range(len(s)+1):
    print(s[start:i])
    if s[start:i] in wordDict:
        start = i
if start == len(s):
    return True
return False

예재까지만 해도 잘 작동한다. 하지만, 조금만 생각해보면 반례가 등장한다. 예를 들면,
이와 같이 하나의 wordDict의 element가 다른 element의 substring일 때는 문제가 된다. 위의 경우에서는 루프에서 인덱스가 0일때, "le"가 매치된다는 것을 확인하고 start이 2로 설정된다. 그 후, "etcode"나 이 문자열을 나눈 segment는 존재하지 않기 때문에 제대로 작동하지 않는다.

해답

해답은 DP를 사용하는 것이고, 루프를 돈다는 점은 동일하지만, 0에서 i까지 나누는 segment가 존재하는지를 나타내는 DP배열을 두고, 각 루프 내부에서 루프를 한번 더 돌아 i까지 segment로 나타낼 수 있는지 확인하는 것이다.

코드는 다음과 같다.

dp = [0] * (len(s) + 1)
dp[0] = 1
for i in range(1, len(s) + 1):
    for j in range(0, i):
        if dp[j] and s[j:i] in wordDict:
            dp[i] = True
return dp[-1]

이 코드가 작동하는 이유는 overlapping subproblem이 존재하기 때문이다. leet라는 substring이 word dict를 통한 segment를 나타낼 수 있는지는 leetcode라는 더 큰 문자열이 segment로 표현 될 수 있는지에 대해 직접적인 영향을 미치기 때문에, leet는 overlapping subproblem인 것이다.

배운점

DP에 익숙해지려면 아직 멀었다. 더 많은 문제들을 풀어보고 문제를 더 작은 문제로 쪼개서 생각하고, 그것을 코드로 구현하는 실력을 쌓아야겠다고 생각했다.