Given a string, find out if string follows a given pattern or not without using any regular expressions.
Input: string - GraphTreesGraph pattern - aba Output: a->Graph b->Trees Input: string - GraphGraphGraph pattern - aaa Output: a->Graph Input: string - GeeksforGeeks pattern - GfG Output: G->Geeks f->for Input: string - GeeksforGeeks pattern - GG Output: No solution exists
We can solve this problem with the help of Backtracking. For each character in the pattern, if the character is not seen before, we consider all possible sub-strings and recurse to see if it leads to the solution or not. We maintain a map that stores sub-string mapped to a pattern character. If pattern character is seen before, we use the same sub-string present in the map. If we found a solution, for each distinct character in the pattern, we print string mapped to it using our map.
Below is C++ implementation of above idea –
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.