So the question is:
Two strings are given A and B
You have to find whether A is substring of B?
1.ow you can change ‘a’ to ‘o’ or ‘t’ to ‘l’ in string A;
2.you can also erase one character from string A.
You can also erase maximum of K characters form string B while matching.
example:
A=“sabcde”
B=“aabacd”
erase one character ‘s’ from A.
now in string B you can erase ‘a’ at index 3 so the abcd substring from index 1 to 5
matches with A.
I used recursive method but didn’t work can anyone tell me was recursion the correct way to proceed or there was probably a ad-hoc solution for this?
you have to use heare dynamic programing …where you have complexity of
O(m*n) and you can esily solve that one by just applying it .
you can also go through my submission for edit distance problem
Question link–>> CMHARD1 Problem - CodeChef
my solution–>>> CodeChef: Practical coding for everyone
you can also go through this vidio of geeksforgeeks
vidio link–>> Dynamic Programming | Set 5 (Edit Distance) | GeeksforGeeks - YouTube
happy coding…!!!
this is general edit distance problem ,but my original question the pattern to be mathced is actually just substring not the entire string .And further you can only delete the character K time