交错字符串(DP)

2020/07/19 12:46
阅读数 45

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

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/interleaving-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

感觉写了快一个月的每日一题,对于算法设计能力的搞还是有点帮助。

今天的困难级别的题目,第一眼没思路,后面想能不能用DP来做?求字符串s3可以分解局部小问题,所以说是可以用DP来写。

用DP就得想出状态转移方程,这次就差边界2和边界3没有想出,其他还是想出了,所以说我的能力应该得到了一丝丝提高。

状态方程:

边界1:dp[0][0] = true;
边界2:if i=0 : dp[0]dp[j] = s2[0-j) equals s3[0,j) 遇到false后面可以直接省略
边界3:if j=0 : dp[i]dp[0] = s1[0-i) equals s3[0,i) 遇到false后面可以直接省略

其他情况,到达(i,j)可能由(i-1,j)点向下一步,选择s1[i-1]到达;也可能由(i,j-1)点向右一步,选择s2[j-1]到达;
dp[i,j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])

该题类似于走迷宫找出口,可以将s1和s2抽象为两个坐标轴。

题目 当然还可以用DFS来写,不过时间可能超时,所以得加记忆化,详见「手画图解」DFS回溯 及其优化

下面试DP解法。


public class Main {

	public static void main(String[] args) {
		String s1 = "db";
		String s2 = "b";
		String s3 = "cbb";
		System.out.println(isInterleave(s1, s2, s3));
	}
	
    public static boolean isInterleave(String s1, String s2, String s3) {
    	int s1_length = s1.length();
    	int s2_length = s2.length();
    	int s3_length = s3.length();
        if (s1_length + s2_length != s3_length) {
            return false;
        }
    	boolean[][] dp = new boolean[s1_length+1][s2_length+1];
    	dp[0][0] = true;
    	for (int i=1; i<=s1_length; i++) {
    		if (s1.charAt(i-1) == s3.charAt(i-1) && dp[i-1][0]) {
    			dp[i][0] = true;
    		}
    	}
    	for (int j=1; j<=s2_length; j++) {
    		if (s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j-1]) {
    		    dp[0][j] = true;
    		}
    	}
    	for (int i=1; i<=s1_length; i++) {
    		for (int j=1; j<=s2_length; j++) {
    			if ((dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1))
                    || (dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1)))
                    dp[i][j] = true;
    		}
    	}
    	return dp[s1_length][s2_length];
	}
    
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部