7

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):

String: DABBCDDE

Pattern: ABD

Possible ways (bolded characters are where the pattern is matched with the string):

  • DABBCDDE
  • DABBCDDE
  • DABBCDDE
  • DABBCDDE

Example 2 (0 matches):

String: ABC

Pattern: BCA

(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)

Base cases:

  • 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?

Daniel Olsson
  • 181
  • 3
  • Are duplicate values allowed in the pattern? Are we guaranteed both pattern and string are in order? – Brandon Arnold Mar 09 '16 at 17:39
  • Yes duplicate values are allowed in the pattern. I don't know if I made myself too clear, but if you scramble the order, then the problem changes. So if you have CBA as string and the pattern is ABC, you have no matches because the first match is the A, and then there are no more characters in the string to match your remaining characters in the pattern (BC). Does it make it clear? – Daniel Olsson Mar 09 '16 at 17:47
  • I find `inserting` quite misleading. Isn't this matching elements in `pattern` with elements in `string` in order in all possible way? – Patrick the Cat Mar 09 '16 at 23:22
  • Deleted my regex answer, because after playing on js fiddle I discovered it doesn't match all possible permutations :( – Gavin Clarke Mar 10 '16 at 07:39
  • 1
    Mai, that is true, I'll change the wording. – Daniel Olsson Mar 10 '16 at 08:53

1 Answers1

1

I think you don't need to use Dynamic Programming to solve this. I think this is the solution :

  1. Firstly make the list of lists to maintain the occurrences of characters in the pattern in the given text.

  2. It will be like this

The following diagram : 

   A    B    D 
             0 
   1 -> 2 -> 5
        3    6

  1. This implies (assuming 0-indexing) A occurs in 0th position, B occurs in 2,3 positions, D occurs in 0,5,6 positions.

  2. For each of the pairs consecutive columns (here A,B and B,D) use pointers to map the corresponding values in a column to the next greater values in the next column. Here 1(in col1) has a pointer to 2(in col2) and 2(in col2) has a pointer to 5(in col3) as 0 is lesser than 2. 3(in col2) has a pointer to 5(in col3)(I couldn't draw here).

  3. For each value in the first column, find the number of possible ways using the pointers. Here 1 -> 2 and 2 -> 5 and so the number of possible ways is 2 * 2 ways (i.e., 1->2->5 , 1->2->6, 1->3->5, 1->3->6). You just have to multiply the number of remaining elements in the column for each value of A.

  4. Here only 1 value for Column1(i.e., A) is present. If there are multiple columns, we calculate the value for each value of A using the pointers and sum all of them to get the number of ways.

  5. I think the complexity is O(n) as to construct list is O(n), pointers space and construction time is O(n).

kaushalpranav
  • 126
  • 2
  • This is correct, but you need to be more specific about generating the occurences of the pattern letters. The complexity for that is O(nm) where n is the pattern length and m the text length. (we need to find all the occurences of each lettern in the pattern). – Adrian Buzea Mar 14 '16 at 14:00