Word Break | Leetcode Day 29

Problem -

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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

"""

Solution -

One possible optimization is that instead of iterating and checking all substrings, we know what len substrings are present in dictionary and we check for only those lengths.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s)+1)
        dp[0] = True
        d = set(wordDict)
        for i in range(len(s)):
            for word in wordDict:
                l = len(word)
                if i+1-l >= 0 and s[i+1-l:i+1] in d and dp[i+1-l]:
                    dp[i+1] = True
                    break
        return dp[-1]