Word Break Problem - How to proceed after creating an array/matrix?

user_19563496 0
Viewed 57

I am trying to solve the Word Break problem on Leetcode and have reached a point wherein I have the following matrix A that contains True if the sequence of letters forms a word on the dictionary and False otherwise.

Code to create the array is below:

word = "catsandog"
wordDict = set(["cats","dog","sand","and","cat"])

n = len(word)

A = [[False] * n for i in range(n)]

for i in range(n+1):
    for j in range(n+1):
        if j > i:
            if word[i:j] in wordDict:
                 A[i][i:j] = [True] * len(A[i][i:j])

However I am unable to figure out how to proceed from here. I understand the output of the code should be False since "cats", "and", "og" is not a space separated word and neither is "cat", "sand", "og", but I am unable to figure how do I incorporate this logic using my matrix A. Any help would be appreciated.

dynamic-programming data-structures algorithm python
1 Answers

I don't believe you need 2D matrix for this, here is the simple approach that I'll use.

def wordBreak(s: str, words: List[str]) -> bool:
    dp = [True] + [False] * len(s) # dp[i] means s[:i+1] can be segmented into words
        
    dp[0] = True
        
    for i in range(len(s)):
        for j in range(i, len(s)):
            if dp[i] and s[i: j+1] in words:
                dp[j+1] = True     #
                
                
                    
    return dp[-1]
    

s = "atepietea"
words = ["tea", "pie", "ate"]
print(wordBreak(s, words))          # True
user_107607680
Related