首页 > 编程学习 > leetcode97-交错字符串

leetcode97-交错字符串

发布时间:2022/8/23 21:18:11

交错字符串

  • dp

定义一个二维的dp数组,表示s1选取 i 个字符和s2选取 j 个字符组成s3的前 i+j 个字符能否成立。

dp递归方程:

  1. 如果i == 0 && j == 0,表示没有任何字符,true
  2. 如果i == 0,那么dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1),dp状态取决于s2的字符和s3的字符是否相同
  3. 如果j == 0,那么dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1),dp状态取决于s1的字符和s3的字符是否相同
  4. 如果 i 和 j 都不等于0,那么s3当前的字符是s1或s2,两个二选一,只要有一个为true则dp状态为true
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), mn = s3.length();
        if(m+n != mn)   return false;
        boolean dp[][] = new boolean[m+1][n+1];
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if(i == 0 && j == 0)    dp[i][j] = true;
                else if(i == 0) dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
                else if(j == 0) dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1);
                else dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
            }
        }
        return dp[m][n];
    }
}
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号