Yet Another Unique Paths
put the strings onto the matrix
+---+---+---+---+---+---+---+
| | * | a | a | b | c | c |
+---+---+---+---+---+---+---+
| * | | | | | | |
+---+---+---+---+---+---+---+
| d | | | | | | |
+---+---+---+---+---+---+---+
| b | | | | | | |
+---+---+---+---+---+---+---+
| b | | | | | | |
+---+---+---+---+---+---+---+
| c | | | | | | |
+---+---+---+---+---+---+---+
| a | | | | | | |
+---+---+---+---+---+---+---+
Paths for aadbbcbcac, from top-left ot bottom-right. each step can choose to go to the grid on the right or the grid on the bottom.
- from
1,1goto1,2use letterainaabcc - from
1,2goto1,3use letterainaabcc - from
1,3goto2,3use letterdindbbca - fork from
2,3, the next step can be2,4or3,3 - ...
- until no next step or reach the bottom right grid.
+---+---+---+---+---+---+---+
| | * | a | a | b | c | c | 0
+---+---+---+---+---+---+---+
| * | 1 | 1 | 1 | | | | 1
+---+---+---+---+---+---+---+
| d | | | 1 | 1 | | | 2
+---+---+---+---+---+---+---+
| b | | | 2 | 1 | 1 | | 3
+---+---+---+---+---+---+---+
| b | | | 2 | | 1 | | 4
+---+---+---+---+---+---+---+
| c | | | 2 | 2 |1 2| | 5
+---+---+---+---+---+---+---+
| a | | | | |1 2|1 2| 6
+---+---+---+---+---+---+---+
0 1 2 3 4 5 6
Paths for aadbbbaccc
+---+---+---+---+---+---+---+
| | * | a | a | b | c | c |
+---+---+---+---+---+---+---+
| * | 1 | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| d | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| b | | | 2 | 1 | | |
+---+---+---+---+---+---+---+
| b | | | 2 | 1 | | |
+---+---+---+---+---+---+---+
| c | | | | | | |
+---+---+---+---+---+---+---+
| a | | | | | | |
+---+---+---+---+---+---+---+
No path can reach the bottom right grid.
P[i][j] indicates that there is an Interleaving String formed by S1[0..i - 1] and S2[0..j - 1].
P[1][1]= trueP[i][j] = (P[i - 1][j] || P[i][j - 1]) && (S3[i + j - 1] == S1[i - 1] || S3[i + j - 1] == S2[j - 1])
I think Dynamic programming is brain fucking. Not as easy as the girds, but, essentially, they are the same.