Determine if a pattern matches with a string or not

Given a string and a pattern, determine if the pattern matches with the string or not. The solution should not use any regex.


 

For example,


Input: 
string – codesleepcode
pattern – XYX

Output:
X: code
Y: sleep

Input: 
string – codecodecode
pattern – XXX

Output:
X: code

 

We can use Backtracking to solve this problem. The idea is for each character in the pattern, we maintain a map that stores sub-string mapped to it. Now if any character is not seen before, we consider all possible sub-strings and recurse to see if it leads to the solution or not. If a solution is found, we print the string mapped to each distinct character in the pattern using the map.

C++

Download   Run Code

Output:

Y: sleep
X: code

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz