I've been thinking about this problem for a while, and I can only find a recursive solution but I'm feeling that there is a dynamic programming way to do it, I just can't figure it out. Is this a famous problem I don't know about?
Q: Given a string and a pattern , return the number of unique ways of matching the letters of the pattern (in order) with the string.
Clarification: To find a match, you take the first character of the pattern, find the first matching character in the string, then you take the second character of the pattern and match with the first matching character of the string that is AFTER your previously matched character.
Example 1 (4 matches):
Possible ways (bolded characters are where the pattern is matched with the string):
Example 2 (0 matches):
(You match B, C and then you're at the end of the string, you can NOT go back and match with previous characters)
With the recursive approach, I have a method which keeps track of which index I'm at on the string (sIndex) as well as the pattern (pIndex). If string[sIndex] match pattern[pIndex], we call the method again and increase sIndex and pIndex. If not - just increase sIndex and try again to find a match. The method returns the total number then because the return value of the recursive calls are added together. (Matches add 1, no matches add 0)
If pIndex is larger than the length of the pattern, return 0.
If sIndex is larger than the length of the string, return 1 (we found a match!)
What other solutions are there?