Question

How to check whether a string can be segmented into a sequence of words from a dictionary in Python

Answer 1

def word_break(s, word_dict):
    n = len(s)
    result = [False] * (n + 1)
    result[0] = True  # empty string is always segmentable

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

    return result[n]


word_dict = {"future", "depends", "the", "on", "your", "dreams", "start", "today"}
s = "futuredependsonyourdreams"

if word_break(s, word_dict):
    print("The string can be segmented")
else:
    print("The string cannot be segmented")



'''
run:

The string can be segmented

'''

 

70+ SQL courses for beginners and professionals

Answer 2

def is_in_dict(word, dictionary):
    return word in dictionary

def word_break(s, result, dictionary):
    for i in range(1, len(s) + 1):
        sub_str = s[:i]
        if is_in_dict(sub_str, dictionary):
            if i == len(s):
                print(result + sub_str)
                return
            word_break(s[i:], result + sub_str + " ", dictionary)


s = "butterflyplaybasketballwithbags"
dictionary = {
      "butterfly", "basketball", "bagpiper", "and", "play",
      "with", "butter", "fly", "basket", "ball", "bags"
  }

word_break(s, "", dictionary)




'''
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

'''

 

70+ SQL courses for beginners and professionals