【LeetCode】Interleaving String 解题报告

【题目】

Givens1,s2,s3, find whethers3is formed by the interleaving ofs1ands2.

For example,Given:s1="aabcc",s2="dbbca",

Whens3="aadbbcbcac", return true.Whens3="aadbbbaccc", return false.

【解析】

题意：有两个字符串s1和s2，每次从这两个字符串中的一个中取出一个字符（从前往后取），直到两个字符串都取完，这样可以组成很多新的字符串，问s3是否属于这些新组成的字符串中的一个。

暴力递归法是最直接的想法，但会超时。

动态规划法最关键的是找动规方程，换句话说如何构造二维数组，以及二维数组dp[i][j]表示什么含义。

下面代码中 dp[i][j] 表示 s2 的前 i 个字符和 s1 的前 j 个字符是否匹配 s3 的前 i+j 个字符。

初始化dp[0][0]=0，dp[0][j]表示s2取0个，即s1的前j个字符是否匹配s3的前j个字符；dp[i][0]表示s1取0个，即s2的前i个字符，是否匹配s3的前i个字符。

动规方程：dp[i][j] = dp[i – 1][j] && s2[i – 1] == s3[i + j – 1] || dp[i][j – 1] && s1[i][j – 1] == s3[i + j – 1] ，意思是如果s2的前i-1个字符和s1的前j个字符已经和s3的前i+j-1个字符匹配且s2的第i个字符等于s3的第i+j个字符，或者s2的前i个字符和s1的前j-1个字符已经和s3的前i+j-1个字符匹配，，且s1的第j个字符等于s3的第i+j个字符，那么s2的前i个字符和s1的前j个字符能否与s3的前i+j-1个字符匹配。

【Java代码】

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[s2.length() + 1][s1.length() + 1];dp[0][0] = true;for (int j = 1; j <= s1.length(); j++) {dp[0][j] = dp[0][j – 1] && (s1.charAt(j – 1) == s3.charAt(j – 1));}for (int i = 1; i <= s2.length(); i++) {dp[i][0] = dp[i – 1][0] && (s2.charAt(i – 1) == s3.charAt(i – 1));}for (int i = 1; i <= s2.length(); i++) {for ( int j = 1; j <= s1.length(); j++) {dp[i][j] = dp[i – 1][j] && (s2.charAt(i – 1) == s3.charAt(i + j – 1))|| dp[i][j – 1] && (s1.charAt(j – 1) == s3.charAt(i + j – 1));}}return dp[s2.length()][s1.length()];}}

参考https://leetcode.com/discuss/22726/dp-solution-in-java

关于爱情的句子：情不知所起，一往而情深。