[小米OJ] 6. 交叉队列

思路：

大概思想如下：
1. 动态规划求解，构造dp[][] 二维数组；
2. 设dp[i][j], i 为第一个字符串的第i个字母；j 为第二个字符串的第j个字母
3. dp[i][j] 如果为 1 ，表示 s1[i] 等于 s3[i+j] 且 dp[i−1][j] 等于 1，同理s2
4. 简单的说 dp[i][j] 为 1 就表示这个点可达，以 dp[0][0] 为起点, dp[len1][len2] 为终点，dp数组中值为 1 的点为路径，向下走表示取 s1 的字符，向右走表示取 s2 的字符。这样就将抽象的字符组合转化成了更好理解的二维数组来表示；
5. 最优子结构即为： s1,s2 的 i,j 点字符之前的字符能否交叉组合成字符串 s3 的前 i+j 个字符，转换到二维数组即为，i,j 点左侧点和上方的点是否可达。

    private static String solution(String line) {

        String[] strs = line.split(",");

        int len0 = strs[0].length();

        int len1 = strs[1].length();

        int len2 = strs[2].length();

        if (len0 + len1 != len2)

            return false + "";

        int dp[][] = new int[len0 + 1][len1 + 1];

        // init

        dp[0][0] = 1;

        for (int i = 1; i <= len0; i++) {

            if (strs[0].charAt(i - 1) == strs[2].charAt(i - 1))

                dp[i][0] = dp[i - 1][0];

            else

                break;

        }

        for (int i = 1; i <= len1; i++) {

            if (strs[1].charAt(i - 1) == strs[2].charAt(i - 1))

                dp[0][i] = dp[0][i - 1];

            else

                break;

        }

        for (int i = 1; i <= len0; i++) {

            for (int j = 1; j <= len1; j++) {

                int k = i + j;

                if (strs[0].charAt(i - 1) == strs[2].charAt(k - 1) && dp[i - 1][j] == 1)

                    dp[i][j] = 1;

                if (strs[1].charAt(j - 1) == strs[2].charAt(k - 1) && dp[i][j - 1] == 1)

                    dp[i][j] = 1;

            }

        }

        if (dp[len0][len1] == 1)

            return true + "";

        return false + "";

    }

巴特西

[小米OJ] 6. 交叉队列

最新文章

热门文章