Leetcode — 139. Word Break

We gonna solve Leetcode 139. Work Break Medium problem. This question is medium but very easy by using the DP solution. We need to understand the question structure first.

Question :

139. Word Break

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.

Note:

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

You may assume the dictionary does not contain duplicate words.

Example 1:

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

This question just a Yes/No question.

Decision Problem: Yes / No question.

We can go into detail about the “leetcode” word.

1 -) We need extra space storage to keep that whether valid or not valid word segment. This store length will be string length. Like :

in the Python: 
table = [False]*(len(s)+1)

Our table will be :

table = [F,F,F,F,F,F,F,F,F]
           l,e,e,t,c,o,d,e

2-) As seen in the table store, we can set the first character as True.

table = [T,F,F,F,F,F,F,F,F]
           l,e,e,t,c,o,d,e

3-) We need to check in a hash map from our Dictionary.

hmap = {}
for word in wordDict:
   hmap[word] = 1

Our Hash Map will be:

hmap : {‘leet’: 1, ‘code’: 1}

3-) Start 2 nested (i,j) Iterate for every each char to check other combinations of words.

for i in range(1,len(table)):
   for j in range(0,i+1):
   if table[j] and s[j:i] in hmap:
        table[i] = True
        break
like "leetcode"
i:1, j= 0 > s[j:i] > "l" check 
j:1, i:1  > s[j:i] > "x"
j :  0  - i :  2 > s[j:i] > "le" check hash map 

First matching will be the “leet” segment,

Finally out table will be :

[True, False, False, False, True, False, False, False, False]

And the second match will be the “code” segment.

[True, False, False, False, True, False, False, False, True]

Our code :