首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

算法:29.交叉字符串

https://www.lintcode.com/problem/interleaving-string/description

描述

给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。

样例

比如 s1 ="aabcc"s2 ="dbbca"

- 当 s3 ="aadbbcbcac",返回 true.

- 当 s3 ="aadbbbaccc", 返回 false.

挑战

要求时间复杂度为O(n^2)或者更好

思路

在s3中交替搜索s1,s2的子串,如果能轮番找到子串,并刚好搜索完三个字符串则返回true。关键在于搜索失败时的搜索位置回退。

代码

小结

代码较短,但是耗时稍长,暂时想不到提升的办法。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180612G1UFDE00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券