Word Break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
"""
Given a non-empty string s and a dictionary wordDict 

containing a list of non-empty words,

determine if it 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.

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.

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

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    """
    this can be broken down to subproblems
    if we know a string is ok up to the 42nd index, it's enough to check from there 
    a list can keep track of this, ok = []
    if up to ith index of s is ok, ok[i] will be True 
    eg. 
    s="cars" 
    wordDict = [car, ca, rs]
    start walking from the start
    ok = [t,f,f,f,f,f]
    c, ca -> yes ca in dict, so ok becomes [t,f,t,f,f]
    a, ar, ars nope
    r, rs -> yes rs in dict, ok becomes [t,f,t,f,t]
    """

    ok = [True] + [False] * (len(s))

    for i in range(1,len(s)+1): 
        for j in range(i): # j is the start index
            # start point has to be ok, 
            # otherwise starting from here does not make sense
            if ok[j] and s[j:i] in wordDict: 
                    # we are ok up to index j 
                    ok[i] = True
                    break 
    return ok[-1]