Java实现交替字符串

1 问题描述

输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成且不改变s1和s2中各个字符原有的相对顺序。

2 解决方案

此处采用动态规划法，可以较大的提高时间效率。

package com.liuzhen.practice;

public class Main {

    public boolean judge(String A, String B, String C) {

        if(C.length() != A.length() + B.length())

            return false;

        int[][] dp = new int[A.length() + 1][B.length() + 1];

        dp[0][0] = 1;  //代表A和B均为空串时，C也为空串，此时符合交替字符串匹配

        for(int i = 0;i <= A.length();i++) {

            for(int j = 0;j <= B.length();j++) {

                if((i - 1 >= 0 && dp[i-1][j] == 1 && A.charAt(i-1) == C.charAt(i+j-1))||

                  (j - 1 >= 0 && dp[i][j-1] == 1 && B.charAt(j-1) == C.charAt(i+j-1)) )

                    dp[i][j] = 1;

            }

        }

        if(dp[A.length()][B.length()] == 0)

            return false;

        return true;

    }

    public static void main(String[] args) {

        Main test = new Main();

        String A = "aabcc";

        String B = "dbbca";

        String C = "aadbbbccca";

        if(test.judge(A, B, C))

            System.out.println("符合交替字符串");

        else

            System.out.println("不符合交替字符串");

    }

}

运行结果：

符合交替字符串

巴特西

Java实现交替字符串

最新文章

热门文章