Program to check a string can be broken into given list of words or not in python

Suppose we have a word list and another string s with no spaces. We have to check whether the string can be broken down using the list of words or not.

So, if the input is like words = ["love", "python", "we", "programming", "language"] s = "welovepythonprogramming", then the output will be True

To solve this, we will follow these steps −

• words := a new set of all unique words
• Define a function rec() . This will take i
• if i is same as size of s , then
  • return True
• acc := blank string
• for j in range i to size of s, do
  • acc := acc concatenate s[j]
  • if acc is in words, then
    • if rec(j + 1) is True, then
      • return True
• return False
• From the main method call rec(0) and return result

Let us see the following implementation to get better understanding −

Example 

Live Demo

class Solution:    def solve(self, words, s):       words = set(words)       def rec(i=0):          if i == len(s):             return True          acc = ""          for j in range(i, len(s)):             acc += s[j]             if acc in words:                if rec(j + 1):                   return True          return False       return rec()       ob = Solution() words = ["love", "python", "we", "programming", "language"] s = "welovepythonprogramming" print(ob.solve(words, s))

Input

["love", "python", "we", "programming", "language"], "welovepythonprogramming"

Output

True