【LeetCode】47 交错字符串
< 返回列表时间: 2020-06-27来源:OSCHINA
题目


解题思路:
思路:动态规划
暂时不是很懂
https://leetcode-cn.com/problems/interleaving-string/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-9/
代码: import java.util.*; public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if (s1.length() + s2.length() != s3.length()) { return false; } boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { for (int j = 0; j <= s2.length(); 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(j - 1); } else if (j == 0) { dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 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[s1.length()][s2.length()]; } }
热门排行