AlgoViz Lab交互式算法学习Algorithms first
交错字符串 · 交互式算法学习
判断 s3 是否由 s1、s2 保持各自顺序交错组成。
#97 · 多维动态规划
交错字符串
Interleaving String
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"状态表3 个关键状态
步骤 1dp[0][0]=true。
base01230
a
a
d
b
1b
c
b
c
2a
c
当前状态转移来源
推荐
二维 DP
时间
O(mn)空间 O(n)dp[i][j] 表示 s1 前 i 个与 s2 前 j 个能否组成 s3 前 i+j 个。
1function isInterleave(a, b, c) {2 if (a.length + b.length !== c.length) return false;3 const dp = Array(b.length + 1).fill(false);4 dp[0] = true;5 for (let i = 0; i <= a.length; i++)6 for (let j = 0; j <= b.length; j++) {7 if (i) dp[j] = dp[j] && a[i - 1] === c[i + j - 1];8 if (j) dp[j] = dp[j] || dp[j - 1] && b[j - 1] === c[i + j - 1]9 }10 return dp[b.length];11}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 private Map<List<Integer>, Boolean> f = new HashMap<>();3 private String s1;4 private String s2;5 private String s3;6 private int m;7 private int n;8 9 public boolean isInterleave(String s1, String s2, String s3) {10 m = s1.length();11 n = s2.length();12 if (m + n != s3.length()) {13 return false;14 }15 this.s1 = s1;16 this.s2 = s2;17 this.s3 = s3;18 return dfs(0, 0);19 }20 21 private boolean dfs(int i, int j) {22 if (i >= m && j >= n) {23 return true;24 }25 var key = List.of(i, j);26 if (f.containsKey(key)) {27 return f.get(key);28 }29 int k = i + j;30 boolean ans = false;31 if (i < m && s1.charAt(i) == s3.charAt(k) && dfs(i + 1, j)) {32 ans = true;33 }34 if (!ans && j < n && s2.charAt(j) == s3.charAt(k) && dfs(i, j + 1)) {35 ans = true;36 }37 f.put(key, ans);38 return ans;39 }40}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
交错字符串 · 解法对比
判断 s3 是否由 s1、s2 保持各自顺序交错组成。
- 测试用例
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"- 题目分类
- 多维动态规划
- 解法对比
- 2
递归选择来源
s3 当前字符若能匹配 s1 或 s2，就递归对应下一位置。
- 时间
O(2^(m+n))- 空间
O(m+n)
二维 DP
dp[i][j] 表示 s1 前 i 个与 s2 前 j 个能否组成 s3 前 i+j 个。
- 时间
O(mn)- 空间
O(n)