【LeetCode】97. Interleaving String
LeetCode string 97
2023-09-11 14:20:27 时间
Interleaving String
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.
可以用递归做,每匹配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: bool isInterleave(string s1, string s2, string s3) { int m = s1.size(); int n = s2.size(); if(m+n != s3.size()) return false; vector<vector<bool> > path(m+1, vector<bool>(n+1, false)); for(int i = 0; i < m+1; i ++) { for(int j = 0; j < n+1; j ++) { if(i == 0 && j == 0) // start path[i][j] = true; else if(i == 0) path[i][j] = path[i][j-1] & (s2[j-1]==s3[j-1]); else if(j == 0) path[i][j] = path[i-1][j] & (s1[i-1]==s3[i-1]); else path[i][j] = (path[i][j-1] & (s2[j-1]==s3[i+j-1])) || (path[i-1][j] & (s1[i-1]==s3[i+j-1])); } } return path[m][n]; } };
相关文章
- Leetcode: Number of Segments in a String
- Leetcode: Decode String
- Leetcode: Group Shifted Strings
- Leetcode: Interleaving String
- Leetcode: Reverse Words in a String
- Leetcode: First Missing Positive
- (LeetCode)用两个栈实现一个队列
- LeetCode高频题66. 加一,给你一个数组表示数字,则加1返回结果
- LeetCode高频题:图像交并比IoU计算方法和手撕代码
- 【Leetcode】1143. 最长公共子序列(中等)
- Leetcode 85.最大矩形(困难)
- Leetcode 684.冗余连接(中等)
- [LeetCode] String to Integer (atoi)
- JAVA字符串格式化-String.format()的使用 及 Android 中 string.xml 中 字符串格式转化
- 【LeetCode】62. Unique Paths
- [LeetCode] 1298. Maximum Candies You Can Get from Boxes 你能从盒子里获得的最大糖果数
- [LeetCode] 1221. Split a String in Balanced Strings 分割平衡字符串
- [LeetCode] 1175. Prime Arrangements 质数排列
- [LeetCode] 1016. Binary String With Substrings Representing 1 To N 子串能表示从1到N数字的二进制串
- [LeetCode] 926. Flip String to Monotone Increasing 翻转字符串到单调递增
- [LeetCode] 844. Backspace String Compare 退格字符串比较
- [LeetCode] 835. Image Overlap 图像重叠
- [LeetCode] 785. Is Graph Bipartite? 是二分图么?
- [LeetCode] Reverse String II 翻转字符串之二
- [LeetCode] 344. Reverse String 翻转字符串
- [LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二
- [LeetCode] Move Zeroes 移动零
- [LeetCode] Candy 分糖果问题