当前位置:网站首页>969 interlaced string
969 interlaced string
2022-07-02 00:57:00 【-Lin Zeyu】
The title is as follows
Given three strings s1、s2、s3, Please help to verify s3 Is it by s1 and s2 staggered Composed of .
Two strings s and t staggered The definition and process are as follows , Each of these strings is split into several Non empty Substring :
s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
staggered yes s1 + t1 + s2 + t2 + s3 + t3 + … perhaps t1 + s1 + t2 + s2 + t3 + s3 + …
Be careful :a + b It means string a and b Connect .
Example 1:
Input :s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
Output :true
Example 2:
Input :s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
Output :false
Example 3:
Input :s1 = “”, s2 = “”, s3 = “”
Output :true
Tips :
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、 and s3 It's all made up of lowercase letters
How to solve the problem 1
Dynamic programming
class Solution
{
public:
bool isInterleave(string s1, string s2, string s3)
{
auto f = vector < vector <int> >(s1.size() + 1, vector <int>(s2.size() + 1, false));
int n = s1.size(), m = s2.size(), t = s3.size();
if (n + m != t)
{
return false;
}
f[0][0] = true;
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
int p = i + j - 1;
if (i > 0)
{
f[i][j] |= (f[i - 1][j] && s1[i - 1] == s3[p]);
}
if (j > 0)
{
f[i][j] |= (f[i][j - 1] && s2[j - 1] == s3[p]);
}
}
}
return f[n][m];
}
};
It is not difficult to see that the time complexity and space complexity of this implementation are O(nm).
Use rolling arrays to optimize spatial complexity . Because the array here ff Of the ii Line only and No i - 1i−1 Row correlation , So we can optimize this dynamic programming with rolling array , In this way, the spatial complexity can become O(m).
An optimization method
class Solution
{
public:
bool isInterleave(string s1, string s2, string s3)
{
auto f = vector <int>(s2.size() + 1, false);
int n = s1.size(), m = s2.size(), t = s3.size();
if (n + m != t)
{
return false;
}
f[0] = true;
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
int p = i + j - 1;
if (i > 0)
{
f[j] &= (s1[i - 1] == s3[p]);
}
if (j > 0)
{
f[j] |= (f[j - 1] && s2[j - 1] == s3[p]);
}
}
}
return f[m];
}
};
Complexity analysis
Time complexity :O(nm), The time cost of the double cycle is O(nm).
Spatial complexity :O(m), namely s 2 The length of .
边栏推荐
- Node——Egg 创建本地文件访问接口
- Mitsubishi PLC FX3U pulse axis jog function block (mc_jog)
- [leetcode] number of maximum consecutive ones
- 测试人进阶技能:单元测试报告应用指南
- 449 original code, complement code, inverse code
- How to open an account for individual stock speculation? Is it safe?
- Common loss function of deep learning
- Global and Chinese markets for the application of artificial intelligence in security, public security and national security 2022-2028: Research Report on technology, participants, trends, market size
- AIX存储管理之总结篇
- [eight sorts ①] insert sort (direct insert sort, Hill sort)
猜你喜欢
Leetcode question brushing: stack and queue 07 (maximum value of sliding window)
2022拼多多详情/拼多多商品详情/拼多多sku详情
Otaku wallpaper Daquan wechat applet source code - with dynamic wallpaper to support a variety of traffic owners
AIX存储管理之逻辑卷的创建及属性的查看和修改
Leetcode skimming: stack and queue 04 (delete all adjacent duplicates in the string)
Geek DIY open source solution sharing - digital amplitude frequency equalization power amplifier design (practical embedded electronic design works, comprehensive practice of software and hardware)
Leetcode skimming: binary tree 02 (middle order traversal of binary tree)
2022 safety officer-b certificate examination practice questions simulated examination platform operation
【会议资源】2022年第三届自动化科学与工程国际会议(JCASE 2022)
Leetcode skimming: stack and queue 02 (realizing stack with queue)
随机推荐
Node——生成微信权限验证配置
[opencv450] hog+svm and hog+cascade for pedestrian detection
SSO single sign on implementation.
使用 ES 实现疫情地图或者外卖点餐功能(含代码及数据)
King combat power query renamed toolbox applet source code - with traffic main incentive advertisement
How to extract login cookies when JMeter performs interface testing
Viewing and modifying volume group attributes of Aix storage management (II)
[conference resources] the Third International Conference on Automation Science and Engineering in 2022 (jcase 2022)
2023 Lexus ES products have been announced, which makes great progress this time
Random avatar encyclopedia, multi category wechat applet source code with history_ Support traffic master
2022 pinduoduo details / pinduoduo product details / pinduoduo SKU details
【会议资源】2022年第三届自动化科学与工程国际会议(JCASE 2022)
Global and Chinese markets for maritime services 2022-2028: Research Report on technology, participants, trends, market size and share
Global and Chinese markets for context and location-based services 2022-2028: Research Report on technology, participants, trends, market size and share
export default 导出的对象,不能解构问题,和module.exports的区别
What skills does an excellent software tester need to master?
程序员该如何更好的规划自己的职业发展?
Bilstm CRF code implementation
Promise和模块块化编程
Use es to realize epidemic map or take out order function (including code and data)