• 交替字符串
    • 题目描述
    • 分析与解法

    交替字符串

    题目描述

    输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，例如当s1 = “aabcc”，s2 = “dbbca”，s3 = “aadbbcbcac”时，则输出true，但如果s3=“accabdbbca”，则输出false。

    分析与解法

    此题不能简单的排序，因为一旦排序，便改变了s1或s2中各个字符原始的相对顺序，既然不能排序，咱们可以考虑下用动态规划的方法，令dp[i][j]代表s3[0…i+j-1]是否由s1[0…i-1]和s2[0…j-1]的字符组成

    • 如果s1当前字符（即s1[i-1]）等于s3当前字符（即s3[i+j-1]），而且dp[i-1][j]为真，那么可以取s1当前字符而忽略s2的情况，dp[i][j]返回真；
    • 如果s2当前字符等于s3当前字符，并且dp[i][j-1]为真，那么可以取s2而忽略s1的情况，dp[i][j]返回真，其它情况，dp[i][j]返回假

    参考代码如下：

    1. public boolean IsInterleave(String s1, String 2, String 3){
    2.     int n = s1.length(), m = s2.length(), s = s3.length();
    4.     //如果长度不一致，则s3不可能由s1和s2交错组成
    5.     if (n + m != s)
    6.         return false;
    8.     boolean[][]dp = new boolean[n + 1][m + 1];
    10.     //在初始化边界时，我们认为空串可以由空串组成，因此dp[0][0]赋值为true。
    11.     dp[0][0] = true;
    13.     for (int i = 0; i < n + 1; i++){
    14.         for (int j = 0; j < m + 1; j++){
    15.             if ( dp[i][j] || (i - 1 >= 0 && dp[i - 1][j] == true &&
    16.                 //取s1字符
    17.                 s1.charAT(i - 1) == s3.charAT(i + j - 1)) ||
    19.                 (j - 1 >= 0 && dp[i][j - 1] == true &&
    20.                 //取s2字符
    21.                 s2.charAT(j - 1) == s3.charAT(i + j - 1)) )
    23.                 dp[i][j] = true;
    24.             else
    25.                 dp[i][j] = false;
    26.         }
    27.     }
    28.     return dp[n][m]
    29. }

    理解本题及上段代码，对真正理解动态规划有一定帮助。