Leetcode - 139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

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

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique

class Trie:
    def __init__( self ):
        self.is_word = False
        self.children = {}
        
    def add_words( self, words ):
        for word in words:
            curr = self
            
            for ch in word:
                if ch not in curr.children:
                    curr.children[ch] = Trie()
                    
                curr = curr.children[ch]
            
            curr.is_word = True
    
class Solution:
    def wordBreak( self, s: str, wordDict: List[str] ) -> bool:
        trie = Trie()
        trie.add_words( wordDict )
        n = len( s )
        p = [ False ] + [ True ] * ( n )
        
        for i in range( n ):
            if p[i] or s[i] not in trie.children:
                continue
            
            curr = trie
            for j in range( i, n ):
                if s[j] not in curr.children:
                    break
                    
                curr = curr.children[ s[j] ]
                    
                if curr.is_word:
                    p[ j + 1 ] = False
            
        return not p[-1]