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

Java

Download   Run Code

Output:

X: code
Y: sleep

 
Author: Aditya Goel

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of