Word Break

Question

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

Example 1

None

Solution

▭

all//Word Break.py

def word_break(s, word_dict):
    n = len(s)
    dp = [False for i in range(n+1)]

    for i in range(n+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True

    return dp[n]

# Driver Code
s = "iloveicecream"
word_dict = ["i", "love", "ice", "cream"]
if word_break(s, word_dict):
    print("Yes")
else:
    print("No")

▯

all//Word Break.py

def word_break(s, word_dict):
    n = len(s)
    dp = [False for i in range(n+1)]

    for i in range(n+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True

    return dp[n]

# Driver Code
s = "iloveicecream"
word_dict = ["i", "love", "ice", "cream"]
if word_break(s, word_dict):
    print("Yes")
else:
    print("No")