package cn.edu.algorithm.huawei;public class Solution {    /**     * Determine whether s3 is formed by interleaving of s1 and s2.     *     * @param s1, s2, s3: As description.     * @return: true or false.     */    public boolean isInterleave(String s1, String s2, String s3) {        if (s1.length() + s2.length() != s3.length())            return false;        if (s1 == null || s1.length() == 0)            return s2.equals(s3);        if (s2 == null || s2.length() == 0)            return s1.equals(s3);        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];        char[] arr1 = s1.toCharArray();        char[] arr2 = s2.toCharArray();        char[] arr3 = s3.toCharArray();        dp[0][0] = true;        for (int i = 1; i <= s1.length(); i++) {            if (arr1[i - 1] != arr3[i - 1]) {                break;            }            dp[i][0] = true;        }        for (int j = 1; j <= s2.length(); j++) {            if (arr2[j - 1] != arr3[j - 1]) {                break;            }            dp[0][j] = true;        }        for (int i = 1; i <= s1.length(); i++) {            for (int j = 1; j <= s2.length(); j++) {                if (arr1[i - 1] == arr3[i + j - 1] && dp[i - 1][j] || arr2[j - 1] == arr3[i + j - 1] && dp[i][j - 1]) {                    dp[i][j] = true;                }            }        }        return dp[s1.length()][s2.length()];    }    public static void main(String[] args) {        String s1 = "abbcddef";        String s2 = "accbbbcd";        String s3 = "abbcddefaccbbbcd";        Solution s = new Solution();        System.out.println(s.isInterleave(s1, s2, s3));    }}