97. 交错字符串

问题97 交错字符串 ★★★☆☆

https://leetcode-cn.com/problems/interleaving-string/

我觉得这个题目有点难度，光是题目要求就需要理解消化，将两个字符串分别划分为两个子串序列，子串个数相等或者相差为1，然后把两个子串序列交错的拼接成一个字符串，现在给定三个字符串，问是否存在某种划分方式，使得划分以后得到的两个子串序列交错以后可以组成第三个字符串。

这个题目我一开始的思路是递归，尝试编码以后发现超时。其实如果有更好的解题直觉，直接从动态规划入手，状态转移方程并不难想到。我们定义dp[m][n]，其中dp[i][j]表示s1的前i个字符和s2的前j个字符是否能划分并交错组成s3的前i+j个字符。那么dp[i][j]的计算和dp[i-1][j]、dp[i][j-1]、s1[i-1]、s2[j-1]、s3[i+j-1]有关。

	public boolean isInterleave(String s1, String s2, String s3) {
		assert s1 != null && s2 != null && s3 != null;

		int len1 = s1.length();
		int len2 = s2.length();
		int len3 = s3.length();

		if (len1 + len2 != len3) {
			return false;
		}

		if (len1 == 0 && len2 == 0 && len3 == 0) {
			return true;
		}

		boolean[][] dp = new boolean[len1 + 1][len2 + 1];

		int matches1 = matches(s1, s3);
		for (int len = 1; len <= matches1; len++) {
			dp[len][0] = true;
		}

		int matches2 = matches(s2, s3);
		for (int len = 1; len <= matches2; len++) {
			dp[0][len] = true;
		}

		for (int sum = 2; sum <= len1 + len2; sum++) {
			for (int i = 1; i <= sum; i++) {
				int j = sum - i;

				if (i <= 0 || i > len1 || j <= 0 || j > len2) {
					continue;
				}

				if (s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
					dp[i][j] = dp[i][j] || dp[i - 1][j];
				}
				if (s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
					dp[i][j] = dp[i][j] || dp[i][j - 1];
				}
			}
		}

		return dp[len1][len2];
	}
	
		private int matches(String s, String t) {
		int cnt = 0;
		for (int i = 0, j = 0; i < s.length() && j < t.length(); i++, j++) {
			if (s.charAt(i) == t.charAt(j)) {
				cnt++;
			} else {
				break;
			}
		}

		return cnt;
	}

在 LeetCode 查看