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.
[balabala] 像所有题目一样,先从暴力直接法入手,这有助于打开思路,然后再想优化。做题时是明确这题属于DP类题目的,因此就套用DP的思考模式,要求得目标,我需要储备什么信息呢? 暴力法通常蕴含最本质的思路,即使使用DP技巧也是需要的,这题目最基本的思路就是s3的一个字符要么匹配s1的一个字符,要么匹配s2的,否则可直接判定为false。DP思路通常可以从最后一步来推导递推公式,s3如果确实由s1, s2混插得到,则要么s1[0, n1 - 2] + s2 [0, n2 - 1] = s3[0, n1 + n2 - 1]且s3最后一个字符是s1的最后一个字符,要么s1[0, n1 - 1] + s2 [0, n2 - 2] = s3[0, n1 + n2 - 1]且s3最后一个字符是s2的最后一个字符,如此就可推广到一般情况从而获得递推公式。
// Method 2: DP public boolean isInterleave(String s1, String s2, String s3) { if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) return false; int n1 = s1.length(), n2 = s2.length(), n3 = s3.length(); boolean[][] dp = new boolean[n1 + 1][n2 + 1]; dp[0][0] = true; for (int j = 1; j <= n2; j++) { dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1); } for (int i = 1; i <= n1; i++) { dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1); for (int j = 1; j <= n2; j++) { dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)); } } return dp[n1][n2]; } // Method 1: Brute Force public boolean isInterleave(String s1, String s2, String s3) { if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) return false; return recur(s1, s2, s3, 0, 0, 0); } private boolean recur(String s1, String s2, String s3, int p1, int p2, int p3) { if (p1 == s1.length() && p2 == s2.length() && p3 == s3.length()) return true; if (p1 < s1.length() && s1.charAt(p1) == s3.charAt(p3)) { if (recur(s1, s2, s3, p1 + 1, p2, p3 + 1)) return true; else if (p2 < s2.length() && s2.charAt(p2) == s3.charAt(p3)) return recur(s1, s2, s3, p1, p2 + 1, p3 + 1); else return false; } else if (p2 < s2.length() && s2.charAt(p2) == s3.charAt(p3)) { return recur(s1, s2, s3, p1, p2 + 1, p3 + 1); } else { return false; } }
相关推荐
js js_leetcode题解之97-interleaving-string.js
LeetCode,作为全球知名的在线编程挑战平台,为学习和实践算法提供了丰富的资源,其上的“leetcode-spider”项目则为程序员提供了一个自动爬取和练习LeetCode算法题目的工具。 一、算法概述 算法,简单来说,就是...
《在IDE中高效进行LeetCode练习:leetcode-editor的深度解析》 在编程学习与技能提升的过程中,LeetCode作为一款广受欢迎的在线编程挑战平台,帮助众多开发者锻炼算法思维,提高编程能力。而为了进一步提升练习体验...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode Editor 7.4 版本的下载是一个名为 "leetcode-editor" 的压缩包文件。这个压缩包的导入过程非常简单,只需要将它直接拖入 IDEA 界面,IDEA 会自动识别并安装插件。这种方式使得安装过程无需额外的步骤,对于...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
python python_leetcode题解之097_Interleaving_String
leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
c语言基础 c语言_leetcode题解之0097_interleaving_string.zip
`swift-Swif-LeetCode-Utils` 是一个实用工具库,它为Swift程序员提供了方便快捷的方法来处理这些问题。这个项目可以帮助你更高效地进行LeetCode上的编程练习,提升你的解决方案的可读性和简洁性。 首先,让我们...
java java_leetcode-115-distinct-subsquences
java java_leetcode-112-path-sum
java java_leetcode-101-symmetric-tree
java java_leetcode-100-same-tree
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb