SSHUFFLE - String Shuffle
Given three strings consisting of just lowercase letters, count the number of ways that the third
string can be constructed by combining two subsequences from the first two strings.
One derives a subsequence of the string by deleting zero or more characters from a string. For example, “”, “a”, “b”, “c”, “ab”, “ac”, “bc”, and “abc” are all the subsequence strings of “abc”. (Note that the empty string, “”, is a subsequence of any string.)
The two subsequences are combined to make a third string by shuffling them together. That is, the relative order of the letters from the subsequence cannot be changed in the target string; but the two subsequences can be interleaved arbitrarily. For example, consider the two subsequences “abc” and “de”. By combining them, one can get the following strings: “abcde”, “abdce”, “abdec”, “adbce”, “adbec”, “adebc”, “dabce”, “dabec”, “daebc”, and “deabc”.
The first line of the input contains a single integer t that indicates the number of test cases. Each test case contains 3 strings, each containing only lowercase characters. The length of each string is between 1 and 60, inclusive.
For each test case, output a line with a single integer that denotes the number of ways that one can construct the third string from the first two strings as described above.
Input: 3 abc abc abc aa aa aa abbcd bccde abcde Output: 8 10 18
Done with a 3-D DP
the answer should not fit in int, but if use int, then you will get AC
Last edit: 2015-06-27 13:50:35
Amruth Kumar Juturu:
Can anyone please give some testcases? Status of my submission shows wrong answer.