转载

[LeetCode] 97. Interleaving String 交错字符串 leetcode java

题目:

给定三个字符串 s1 , s2 , s3 , 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

<strong>输入:</strong> s1 = "aabcc", s2 = "dbbca", <em>s3</em> = "aadbbcbcac"
<strong>输出:</strong> true

示例 2:

<strong>输入:</strong> s1 = "aabcc", s2 = "dbbca", <em>s3</em> = "aadbbbaccc"
<strong>输出:</strong> false

思路：

可以用递归做，每匹配s1或者s2中任意一个就递归下去。但是会超时。

因此考虑用动态规划做。

s1, s2只有两个字符串，因此可以展平为一个二维地图，判断是否能从左上角走到右下角。

当s1到达第i个元素，s2到达第j个元素:

地图上往右一步就是s2[j-1]匹配s3[i+j-1]。

地图上往下一步就是s1[i-1]匹配s3[i+j-1]。

示例：s1=”aa”,s2=”ab”,s3=”aaba”。标1的为可行。最终返回右下角。

0 a b

0 1 1 0

a 1 1 1

a 1 0 1

代码：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
		if (s3.length() != s1.length() + s2.length())
			return false;

		boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
		dp[0][0] = true;

		for (int i = 1; i <= s1.length() && s1.charAt(i - 1) == s3.charAt(i - 1); i++)
			dp[i][0] = true;

		for (int i = 1; i <= s2.length() && s2.charAt(i - 1) == s3.charAt(i - 1); i++)
			dp[0][i] = true;

		for (int i = 1; i <= s1.length(); i++) {
			for (int j = 1; j <= s2.length(); j++) {
				char c = s3.charAt(i + j - 1);
				if (c == s1.charAt(i - 1) && dp[i - 1][j])
					dp[i][j] = true;

				if (c == s2.charAt(j - 1) && dp[i][j - 1])
					dp[i][j] = true;
			}
		}
		return dp[s1.length()][s2.length()];
	}
}

原文 http://www.lisite.top/2018/07/14/leetcode-97-interleaving-string-交错字符串-leetcode-java/554.html

正文到此结束