Java for LeetCode 097 Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc"
,
s2 = "dbbca"
,
When s3 = "aadbbcbcac"
, return true.
When s3 = "aadbbbaccc"
, return false.
解题思路:
DP问题,JAVA实现如下:
static public boolean isInterleave(String s1, String s2, String s3) { if (s1.length() + s2.length() != s3.length()) return false; boolean[] dp = new boolean[s2.length() + 1]; dp[0] = true; for (int j = 1; j <= s2.length(); j++) dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1); for (int i = 1; i <= s1.length(); i++) { dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1); for (int j = 1; j <= s2.length(); ++j) { dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)); } } return dp[s2.length()]; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。