Solve Word Break Problem using Backtracking in Python

In this tutorial, we are going to solve the Word Break Problem using Backtracking and the programming language we’re using is Python. Here the problem is that we are given a long string of words without any spaces and a dictionary of words with the help of Python programming. We are supposed to break the string or sentence into the possible words present in the dictionary.

Using backtracking to solve the problem

The idea is that we will select a word from the dictionary and search for that word in the string,  if any substring matches with the word then we print it otherwise we move ahead and search for the next word in the dictionary.

For every word selected we search for the first letter of the word in the string, if it is present then we move to the next letter of the word and so on.

We will keep two pointers namely “i” and “j” to keep track of the letters in the word and the string respectively that we have already seen.

Now we will go through the string only once for every word in the dictionary by incrementing the pointer “j”. But we will keep backtracking through the word that has been selected, with the help of the pointer “i”.

Once the first letter of the word is found we will increment “i” till there is a mismatch, in that case, we will set back the value of “i” to 0, and again start searching for the first letter in the rest of the string.

Implementation of the solution

In this example is the string we have taken is

string="iwantindependence"

And the dictionary is

word_dict={0: 'i', 1:"like", 2:"ali",3: "want",4: "pancake",5: "mobile",6: "independence", 
           
  7: "tin" ,8: "icecream",9: "ant", 10:"pen",11: "fNow

Now we will create a function ” break_string”  which will take the word and the string and print the word if it is present in the string. Below is our Python code:

def break_string(word,string):
    
#     initiliasing pointer pointing to the string to 0
    j=0
    
    while(j<len(string)):
        
#         initialising pointer pointing to the word to 0
        i=0
        
        while(i<len(word)):
           
            if word[i]==string[j]:
                
# if i==length of word, then the word selected has been seen till the end
# hence the word matched with the substring
                if(i==(len(word)-1)):
                    print(word)
                    break
                
#                 otherwise we will carry on the search
                else:    
                    i+=1
                    j+=1
                
#           if letters or alphabets don't match 
            else:
#               and string is seen till the end --> break
                if(j==len(string)-1):
                    break
                else:
#                   keep increamenting the string     
                    i=0
                    j+=1

#   Once the word is found --> stop incrementing the string          
        break     
                   
                   

Once we get a letter match we increment both “i” and “j” and continue. If after matching some letters of the word and the rest of the letters don’t match then we come out of the second while loop and put the pointer of the word back to 0.

In case the letters are not matching we keep the pointer of the word “i” =0 only and keep incrementing the pointer “j” of the string.

Pointer “i” is only incremented in case of a match, otherwise is always kept at the start of the word(i=0), while pointer “j” keeps moving ahead.

When “i” is equal to the length of the word, we have matched the entire word, hence the word is found. We print it and come out of the loop.

To call the function we give the string and the words by iterating through the dictionary.

 

for word in word_dict.values():
    
    break_string(word,string)

The output is

i
want
independence
tin
ant
pen

 

Leave a Reply