Suppose that a text can be corrupted in such a way that all

Suppose that a text can be corrupted in such a way that all punctuations and spaces have been deleted. For example, if the original text is “it was the best of times.”, then the corrupted version is itwasthebestoftimes. Given a string S, it is desirable to know if S is a corrupted text. To do this, we have to check if S is a concatenated sequence of valid words. Available to us is a dictionary D that contains all valid words. To check if a word w is in the dictionary, you can do this in Python: w in D. If D contains w, the expression will return True. For example, if the dictionary D is {apple, best, it, of, the, times, was} and S =itwasthebestoftimes, then the answer is True. If given the same dictionary D, S =itwasthebe, then the answer is False. 1. (60 points) Explain why the following program does not quite solve this problem by giving a counter example with some values of S and D for which the program returns a wrong answer. def Check(S, D): if len(S) == 0: return True for i in range(len(S)): if S[0:i+1] in D: return Check(S[i+1:], D) return False 2. (40 points) The problem with Check is it only checks for one match and recursively solves a subproblem. This will return a wrong answer sometimes. You should check for all possibilities. Now, fix Check to give a correct program that solves this problem.

1. Explain why the following program does not quite solve this problem by giving a counter example with some values of S and D for which the program returns a wrong answer.

def Check(S, D):

  if len(S) == 0:

  return True

  for i in range(len(S)):

  if S[0:i+1] in D:

return Check(S[i+1:], D)

  return False

2.The problem with Check is it only checks for one match and recursively solves a subproblem. This will return a wrong answer sometimes. You should check for all possibilities. Now, fix Check to give a correct program that solves this problem.

\"For the second question write in python program.\"

Solution

1, Problem with the given code is once some word w matches in D, we start looking at rest of string in the dictionary and it may not return solution. But it is very well possible that some bigger word w\' ( such that w is substring of w\', and we would have found w\' had we kept on looking and not directly called return Check(S[i+1:], D ) ) is also in D, and that returns the valid solution.

For example :   D = { \'ab\',\'abcd\',\'yo\' } and S = \'abcdyo\'

When we start iteration, we see that \'ab\' is in D, and we call recursively for \'cdyo\' which returns false and we get no solution :( which is very sad :p

But, had we consider \'abcd\', we would have called recursively for \'yo\' thus giving a solution :D

         Another explanation at the starting of question 2

2. Now, lets get the correct code.

def Check(S, D):
   if len(S) == 0:
       return True
   result = False;   #if one is true we are done
   for i in range(len(S)):
       if S[0:i+1] in D:
           result = result or Check(S[i+1:], D)
   return result;

D = { \'ab\':1,\'abcd\':2,\'yo\':3};
S = \'abcdyo\';
print Check(S,D);