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

<p><strong>Note</strong> that the same word in the dictionary may be reused multiple times in the segmentation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;, wordDict = [&quot;leet&quot;,&quot;code&quot;]
<strong>Output:</strong> true
<strong>Explanation:</strong> Return true because &quot;leetcode&quot; can be segmented as &quot;leet code&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;applepenapple&quot;, wordDict = [&quot;apple&quot;,&quot;pen&quot;]
<strong>Output:</strong> true
<strong>Explanation:</strong> Return true because &quot;applepenapple&quot; can be segmented as &quot;apple pen apple&quot;.
Note that you are allowed to reuse a dictionary word.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;catsandog&quot;, wordDict = [&quot;cats&quot;,&quot;dog&quot;,&quot;sand&quot;,&quot;and&quot;,&quot;cat&quot;]
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 300</code></li>
	<li><code>1 &lt;= wordDict.length &lt;= 1000</code></li>
	<li><code>1 &lt;= wordDict[i].length &lt;= 20</code></li>
	<li><code>s</code> and <code>wordDict[i]</code> consist of only lowercase English letters.</li>
	<li>All the strings of <code>wordDict</code> are <strong>unique</strong>.</li>
</ul>

# class Solution:
#     def wordBreak(self, s: str, wordDict: List[str]) -> bool:
#         #bottom up dp.
#         dp= [False] *(len(s)+1)
#         dp[len(s)]= True
#         for i in range(len(dp)-1,-1,-1):
#             for w in wordDict:
#                 if i +len(w) <= len(dp) and s[i:i+len(w)] ==w:
#                     dp[i] = dp[i+len(w)]
#                 if dp[i]:
#                     break
#         return dp[0]



class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        #bottom up dp.
        dp= [0] *(len(s)+1)
        dp[len(s)]=1
        for i in range(len(dp)-1,-1,-1):
            for w in wordDict:
                if i+len(w) <=len(dp) and w == s[i:i+len(w)]:
                    dp[i]=dp[i+len(w)]
                if dp[i]:
                    break
        return dp[0]










class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp= [0]*(len(s)+1)
        # inital dp[0] as true
        dp[0] = 1
        for i in range(len(s)+1):
            for w in wordDict:
                # if i==4: print(s[i-len(w):i])
                # break
                if i >= len(w)  and s[i-len(w):i] ==w:            
                    dp[i] = dp[i-len(w)]
                if dp[i]: #why? 
                    break
        #print(dp)        
        return dp[len(s)]















class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        #bottom up dp.
        dp= [0]*(len(s)+1)
        dp[0] = 1 # no letter base case set to true.
        #dp[0+len(w)] = dp[0] if  
        for i in range(0,len(s)+1):
            for c in wordDict:
                if i >=len(c) and s[i-len(c):i]==c:
                    dp[i] = max(dp[i],dp[i-len(c)])
        print(dp)
        return dp[len(s)]
16700