介绍

总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.

适合人群：

有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。

不适合人群：

算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）

非常不适合人群：

算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）

交叉字符串

题目看这里，leetcode第九十七题，hard难度：
https://leetcode.com/problems/interleaving-string/

强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～

解析

首先huahua list上的下一题其实是44 wildcard matching。但是这道题和day1的题完全是一个套路，甚至还要更简单（好像可以秒杀吧），所以为了不摆烂，我们直接略过，看下一题，也就是今天要做的交叉字符串。那么我们这里首先从未优化的方法开始，这次一共有三个不同的答案：

1. 初次尝试

首先是三维动态规划矩阵。这个比我们常用的二维矩阵还多一维，就让人感觉比较有挑战性。其实基本技巧还是一样的。所以说，刷题首先要弄清楚的事情就是不要背题。你觉得面试官有二维的矩阵不考非要考三维的矩阵是为什么？当然是知道你这个小天才早就把二维矩阵动态规划背的滚瓜烂熟。算法面试的本质是两个人沟通并且解决问题，在这个过程中面试官要看到你真的动脑才行。这堆题变得越来越奇怪就是为了动脑这两个字。背题算什么本事？面试时拿到题什么也不问，闷头刷刷写出最优解，那肯定就是直接被领出去的那个。刷题的时候也要开动脑筋，长此以往才能培养出解题能力。

好，那么言归正传，这道问题的主要思路是利用一个三维矩阵来表达三个字符串之间的关系，每个维度代表一个字符串。我们的目标是判断s1和s2是否能交错组成s3，我们可以将这个大问题转化为一系列子问题的求解。具体来说，我们可以取s1和s2的各一个子串，看它们能否交错组成s3的对应部分。如果能，那么s3这一部分的最后一个字符必须是这个s1或s2子串的最后一个字符。我们通过这种方式，不断对s1和s2取子串，判断是否能交错组成s3。同时，我们还需要处理边界条件，这个时候就需要对s1，s2和s3分别进行单独匹配，以初始化我们的动态规划矩阵。通过这样的方式，我们就能逐步填满这个三维矩阵，最终根据矩阵的最后一位来判断s1和s2是否能交错组成s3。

那么这里的问题是啥呢？总而言之不通过，因为memory用的太多。三维矩阵还是太大，面试官会让你优化一下空间，这也就有了第二个答案：

2. 空间优化

在动态规划中，有一个常用的技巧叫做滚动数组。它的作用是减少我们需要保存的状态数量，从而降低空间复杂度。

在这个问题里，我们观察到状态转移方程中，第k步的状态只依赖于第k-1步的状态，也就是说我们在求解第k步的状态时，并不需要知道第k-2步及以前的状态。这就意味着我们并不需要把所有的状态都保存下来，而只需要保存当前步和上一步的状态就可以了，这就是滚动数组的思想。

但是这里有个小技巧，就是在更新第k步的状态时，我们必须确保第k-1步的状态不会被覆盖。因此，在循环遍历时，我们采用了从后向前的方式，也就是for循环的reverse函数的作用。这样可以保证在计算当前状态时，我们用到的上一步的状态是准确的，没有被错误地更新过。

好，现在新的答案还是不通过，因为耗费了太多时间。面试官继续follow up。那么，是时候展示最终版本了。

3. 时间优化

这个优化技巧并没有很强的通用性，但是它是基于一个很重要的观察。在尝试使用s1和s2的子串来组成s3的过程中，s1和s2的子串长度之和必然等于我们想要形成的s3子串的长度。因此，我们不需要单独地遍历s3，我们只需要保证s1和s2的子串长度之和等于我们要匹配的s3子串的长度。这个观察可以帮助我们减少一次不必要的循环遍历，因此也可以看作是一种剪枝策略。这种策略有时在动态规划的优化中非常有效，通过减少状态空间或者优化状态转移的计算，可以使解决问题的效率大大提高。

好，那么这就是我们的最终算法。如果甚至有读者看到这里，那么恭喜你，你获得了【鬃狮的小红花】*1，这真是值得庆贺的一件事，不论你或我。所以这里推荐一首好听的歌曲，来自安婧_Tiffany的外面的世界！

思考乐园

你可能会疑惑，为什么第三种解法不用reverse函数。是啊，怎么会事呢？这就是今天留给勤奋的你的思考问题，请尽情开动大脑吧～

教材链接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/