经典算法面试题：交错字符串

港控/mmm° 2022-12-31 03:27 74阅读 0赞

今天的题目是个人非常喜欢的一个，题目的名字叫做“Interleaving String”，这个题目是什么意思呢？

#### 理解题意 ####

Interleaving 从字面上讲是交错交叉的意思，给定两个字符串s1:"a"和s2:"b"，那么对于s3:"ab"我们说s3是s1和s2“交错”形成的一个字符串，也就是说对于s3中的一个字符，这个字符要么来自于s1要么来自于s3且s1和s2中的字符只能使用一次。

因此对于s1 = "ab", s2 = "cd", s3 = "acbd"，我们可以说s3可以由s1和s2交错形成，过程是这样的：

*  使用s1的字符a
 *  使用s2的字符c
 *  使用s1的字符b
 *  使用s2的字符d

这样就形成了s3：“acdb"

而对于s1 = "ab", s2 = "cd", s3 = "adbc"我们说s3不可以由s1和s2交错形成，原因很简单，过程是这样的：

*  s3的第一个字符是a，因此必须使用s1的第一个字符a
 *  s3的第二个字符是d，但是此时可以用的s1的字符是b以及s2的字符c，无论选择s1亦或是选择s2都不能形成字符d，因此s3不可以由s1和s2交错形成

理解了题意后你能想到该怎么解决这个问题吗？

#### 解决方法一：最简单解法 ####

通常我们说在面试时针对算法题如果一下想不到最优解可以首先想一个最简单的时间复杂度较高的解法，那么对于这个问题来说最简单的解法是什么呢？

首先我们要意识到，这个问题的本质其实是一个“**组合**”问题，因为字符串s3是由s1和s2合并形成的，因此我们可以把s1和s2通过“交错”这种方式能形成的所有字符串组合出来然后看看s3是不是在这些字符串组合中。

对于s1：“ab”，s2：“cd”来说，我们首先把s1的字符a放到s2中，a可以放到s2的开头、末尾以及c和d的中间，因此形成了\{acd，cad，cda\}。

然后我们需要把s1的b放到上述中间结果中，我们只需要注意一点，那就是b一定要放到a的后面，因此对于中间结果中的acd来说，添加b之后形成的最后结果为\{abcd, acbd, acdb\}。

这样我们就把s1和s2能形成的所有结果都组合出来了，然后再看一下s3是不是在这些结果中就可以了。

这种解法相对简单，不足的地方在于组合过程中需要大量的字符串拼接，同时保留中间结果也占用内存，那么有没有更好的办法吗？

#### 解决方法二：动态规划 ####

希望大家不要一看到动态规划这几个字就不想接着往下看了，动态规划的思想非常简单，那就是“**站在巨人的肩膀上**”，当然在这里的巨人其实指的就是利用之前的计算结果不做重复计算。

让我们再仔细的看一下这个题目，s3字符串是由s1和s2形成的，对于s3中的一个字符**要么来自s1要么来自s2**，这对我们来说有什么启示呢？ 通过下图你就明白了：

![format_png][]

对于s1:"ab", s2:"ac", s3:"aabc"来说，s3的第一个字符a既可以来自于s1也可以来自于s2，只有两种选择，无论选择哪一个我们都会得到一个**新的子问题**，因此我们需要进一步求解这个子问题，在这里我们使用f(i,j)来表示以s1的第i个位置到末尾形成的字符串和s2的第j个位置到末尾形成的字符串能否组合出s3从i+j到末尾形成的字符串。

有了这样的定义，那么我们知道如果s1\[i\]和s3\[i+j\]相同的话，那么我们就得到了一个新的子问题f(i+1, j)，如果我们知道f(i+1, j)的解那么我们当然就能知道f(i, j)，即：

*f(i, j) = f(i+1, j) if s1\[i\] == s3\[i+j\]*

同样的道理如果s2\[j\]与s3\[i+j\]相同的话，那么我们知道：

*f(i, j) = f(i, j+1) if s2\[j\] == s3\[i+j\]*

最终我们需要求解的是f(0, 0)，对此你应该很清楚了吧，这不就是初中数学的递归么，由子问题的解推导出当前问题的解，这就是动态规划。

有了这样的分析，代码就很简单了。

#### 代码实现 ####

bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
    
    
        if (len1 + len2 != len3)
            return false;
        if (s1 == "")
            return s2 == s3;
        if (s2 == "")
            return s1 == s3;
    
    
        vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false));
        dp[len1][len2] = true;
        for(int i=len1-1;i>=0;i--)
            dp[i][len2] = s1[i] == s3[i + len3-len1] && dp[i+1][len2];
        for(int j=len2-1;j>=0;j--)
            dp[len1][j] = s2[j] == s3[j + len3-len2] && dp[len1][j+1];
    
    
        for(int i=len1-1;i>=0;i--)
            for (int j=len2-1;j>=0;j--)
                dp[i][j] = s1[i] == s3[i+j] && dp[i+1][j] || 
                           s2[j] == s3[i+j] && dp[i][j+1];
        return dp[0][0];
    }

这里仅仅就是将上面的递归表达式翻译成代码而已，该算法的时间复杂度为O(s1.length \* s2.length)。

#### 总结 ####

这个算法之所以很好是因为你可以使用多种方法来解决，解决问题即是一门技术也是一门艺术，**你可以不知道最优解，但是你一定要让面试官看到你解决问题的能力**，解决问题的能力才是面试官最看重的，而不是那个时间复杂度很低的"标准答案"。对于这个问题如果你有更好的解法欢迎在公众号留言。

--------------------

**为你推荐**

<table> 
 <tbody> 
  <tr> 
   <td>1，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb986d1cbce0fc753efd9fef7497f1788c981f1769097754a7cdeeb8a9cb5c250d14166a215&amp;idx=2&amp;mid=2247483791&amp;scene=21&amp;sn=456e78baeea0f6cec222c0feea236863#wechat_redirect" rel="nofollow">彻底理解二叉树的遍历</a></td> 
  </tr> 
  <tr> 
   <td colspan="1">2，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98621cbce0f379a61fd68f64bed3e8e2d244235231786e908e7e0682cf349cda98edac7d0&amp;idx=1&amp;mid=2247483775&amp;scene=21&amp;sn=4dba79d9b015123ba58903086c9add60#wechat_redirect" rel="nofollow">彻底理解堆</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">3，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&amp;idx=1&amp;mid=2247483951&amp;scene=21&amp;sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">经典算法题：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&amp;idx=1&amp;mid=2247483951&amp;scene=21&amp;sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">两个有序数组中位数</a></td> 
  </tr> 
  <tr> 
   <td colspan="1">4，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98603cbce0f151539b4123bc354c229ad911df4053b0cd72a805806486740892efc998259&amp;idx=1&amp;mid=2247483741&amp;scene=21&amp;sn=faf6b1e9e064389336546e7dcd555fd1#wechat_redirect" rel="nofollow">送命题：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98603cbce0f151539b4123bc354c229ad911df4053b0cd72a805806486740892efc998259&amp;idx=1&amp;mid=2247483741&amp;scene=21&amp;sn=faf6b1e9e064389336546e7dcd555fd1#wechat_redirect" rel="nofollow">进程切换与线程切换的区别</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">5，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98548cbce0c5e054f9b90cd4004ff5d94b4ffedd87c86716b97de5aadcacf2de8dd4883b2&amp;idx=1&amp;mid=2247483926&amp;scene=21&amp;sn=a5f0097a10385a2ca6be8b9d1903e1b5#wechat_redirect" rel="nofollow">一道决定面试成败的算法题</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">6，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb986a0cbce0fb64a2242783b4f52da4a1c141d606a3433f6a8e2584f59d10c76e7c41d5239&amp;idx=1&amp;mid=2247483902&amp;scene=21&amp;sn=4956ffd8d89934e8ec2c3e3e5f8ccb8b#wechat_redirect" rel="nofollow">一个耗时4小时的内存泄漏问题</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">7，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98552cbce0c44953d79c8d0943aab40aeb9098eeffe533537ac9d23d17922b1826f83465c&amp;idx=1&amp;mid=2247483916&amp;scene=21&amp;sn=89851d1f4a6f53ed0308cd4a4da5881e#wechat_redirect" rel="nofollow">一个耗时36小时的内存异常问题</a><br></td> 
  </tr> 
 </tbody> 
</table>

![format_png 1][]

PS：微信公众号从去年开始限制了留言功能，如果你有任何问题欢迎直接在公众号留言。

[format_png]: /images/20221120/4aadc298be44462cbaeb4d0769a92e9c.png
[format_png 1]: /images/20221120/9539b09e951e41e6b0393feef4016d77.png

发表评论取消回复

表情：

评论列表（有 0 条评论，74人围观）

还没有评论，来说两句吧...

相关阅读

相关经典面试算法题

分别以数组为例写出冒泡排序反转二分查找。这三种经典的算法题，如果你们掌握了集合，也可以通过集合来带入算法。

逃离我推掉我的手/ 2024年04月22日 15:25/ 0 赞/ 7 阅读

相关经典算法面试题：交错字符串

今天的题目是个人非常喜欢的一个，题目的名字叫做“Interleaving String”，这个题目是什么意思呢？理解题意 Interleaving 从字面上讲是交错交

港控/mmm°/ 2022年12月31日 03:27/ 0 赞/ 75 阅读

相关经典面试题：JS常见的排序算法

1. 冒泡排序 // 冒泡排序 // 比较两个相邻的元素，将值大的元素交换至右端 // N个数字要排序完成，总共进行N-1趟排序 func

以你之姓@/ 2022年12月13日 11:29/ 0 赞/ 122 阅读

相关 97. 交错字符串

> 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。 > > 两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会

清疚/ 2022年10月10日 01:56/ 0 赞/ 104 阅读

相关经典算法面试题

1、如何判断链表中是否有环？如果有环的话，如何找出环的入口设置两个指针，一个fast指针，一个slow指针，fast指针每次走两步，slow指针每次走一步，若fast和sl

刺骨的言语ヽ痛彻心扉/ 2022年05月19日 04:36/ 0 赞/ 216 阅读

相关面试题经典算法冒泡排序

冒泡排序: 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发

深碍√TFBOYSˉ_/ 2022年05月18日 09:49/ 0 赞/ 142 阅读

相关动态规划：交错字符串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3

我会带着你远行/ 2022年04月10日 13:41/ 0 赞/ 123 阅读

相关 Java面试经典面试题

1、java事件机制包括哪三个部分？分别介绍。 2、为什么要使用线程池？ 3、线程池有什么作用？ 4、说说几种常见的线程池及使用场景。 5、线程池都有哪几种工作

末蓝、/ 2022年03月28日 05:13/ 0 赞/ 298 阅读

相关 LeetCode 97 交错字符串

题目：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。输入输出：输入: s1 = "aabcc", s2 = "d

ゞ浴缸里的玫瑰/ 2022年03月06日 15:12/ 0 赞/ 141 阅读

相关 [经典面试题]完美洗牌算法

题目有个长度为2n的数组\{a1,a2,a3,…,an,b1,b2,b3,…,bn\}，希望排序后\{a1,b1,a2,b2,….,an,bn\}，请考虑有无时间复杂度o(

傷城~/ 2022年02月01日 19:15/ 0 赞/ 264 阅读