leetcode: Interleaving String

Problem Description:

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution and Precautions:

This is dp problem:

Let F(i, j) denote if s1 of length i and s2 of length j could form s3 of lenght i+j, then we have four cases:
(1) F(i, j) = F(i-1, j)                              if s1[i-1] == s3[i+j-1] && s2[j-1] != s3[i +j -1]
(2) F(i, j) = F(i, j-1)                              if s1[i-1] != s3[i+j-1]  && s2[j-1] == s3[i +j -1]
(3) F(i, j) = F(i-1, j) || F(i, j-1)             if s1[i-1] == s3[i+j-1] && s2[j-1] == s3[i +j -1]
(4) F(i, j) = false                                   if s1[i-1] != s3[i+j-1] && s2[j-1] != s3[i +j -1]

Tips and Divergent thinking:

N/A

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on June 5, 2013