算法: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
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券