动态规划：交错字符串

我会带着你远行 2022-04-10 13:41 124阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTI0NTg2_size_16_color_FFFFFF_t_70][]

我们运用动态规划思想，分析示例1：

s1 = aabcc

s2 = dbbca

s3 = aadbbcbcac

建立动态规划模型 dp\[i+1\]\[j+1\]，开始的值为1，即 dp\[0\]\[0\] = 1。

如果 s3\[i+j\] = s1\[i\] 并且 dp\[i-1\]\[j\] = true，我们则认为这是个可行的路径，将dp\[i\]\[j\]置为true；

如果 s3\[i+j\] = s2\[j\] 并且 dp\[i\]\[j-1\] = true，我们也认为这是个可行的路径，将dp\[i\]\[j\]置为true。

最后的 dp\[i\]\[j\] 即为我们求的结果，若为true，则说明是由交错组成。

代码实现如下：

> class Solution \{  
>     public boolean isInterleave(String s1, String s2, String s3) \{  
>         int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();  
>         if (len3 != len1 + len2)  
>             return false;  
>         boolean dp\[\]\[\] = new boolean\[len1+1\]\[len2+1\];  
>         dp\[0\]\[0\] = true;  
>         for(int i=1; i<=len1; i++)  
>         \{  
>             dp\[i\]\[0\] = (s1.charAt(i-1) == s3.charAt(i-1)) && dp\[i-1\]\[0\];  
>         \}  
>         for(int j=1;j<=len2; j++)  
>         \{  
>             dp\[0\]\[j\] = (s2.charAt(j-1) == s3.charAt(j-1)) && dp\[0\]\[j-1\];  
>         \}  
>         for (int i = 1; i <= len1; i++) \{  
>             for (int j = 1; j <= len2; j++) \{  
>                 dp\[i\]\[j\] = ((s1.charAt(i-1) == s3.charAt(i+j-1) && dp\[i-1\]\[j\]) ||  
>                     (s2.charAt(j-1) == s3.charAt(i+j-1) && dp\[i\]\[j-1\]));  
>             \}  
>         \}  
>         return dp\[len1\]\[len2\];  
>     \}  
> \}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTI0NTg2_size_16_color_FFFFFF_t_70]: /images/20220328/2beccd69a523445d87fe24b5ab30c6f7.png