문제 설명

문자열 s와 문자열 딕셔너리 wordDict가 입력값으로 주어진다. 만약 문자열 s가 wordDict 내에 있는 문자열들로 segment할 수 있다면/나눌 수 있다면, true를 반환한다.

• 딕셔너리에 있는 문자열/단어를 여러 번 사용해도 된다.
• s와 wordDict 내부 단어들은 소문자 영어 글자만 포함한다.

# 예시1
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

# 예시2
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".

문제 출처: https://leetcode.com/problems/word-break/description/

문제 풀이

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo = [False] * (len(s) + 1)
        memo[len(s)] = True # s 문자열의 끝을 벗어나면 s는 wordDict의 단어들을 이용해 segment를 할 수 있다.

        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
            	# wordDict 내의 w 단어와 현재 위치의 합이 s의 길이를 벗어나지 않고,
                # s[i : i + len(w)]이 w와 일치한다면,
                # memo[i + len(w)]에서의 segment 가능 여부를 memo[i]에 할당해준다.
                if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:
                    memo[i] = memo[i + len(w)]
                
                # s[i]에서 wordDict의 단어들로 segment가 가능하다면 더 확인할 필요가 없으므로 break.
                if memo[i]:
                    break

        return memo[0]

Bottom-up 방식으로 index가 문자열 s를 벗어난다면, segment가 가능하다고 설정해둔다. 문자열 s의 끝부터 segment 가능 여부를 확인해간다. memo[0]에 true 값이 들어간다면, 문자열 s가 wordDict 내부의 단어들로 segment가 가능하다는 뜻이다.

Reference

• NeetCode - Word Break - Dynamic Programming - Leetcode 139 - Python