介紹

總而言之是時候利用暑假鍛煉一下算法技術，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎的編程愛好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎，但是還未能順利通過筆試/面試，總覺得算法題目想不明白的你。

不適合人群：

算法入門級選手（一上來就做難題可能并不合適，建議首先專注簡單/中等題目）

非常不適合人群：

算法競賽選手（這種小兒科的問題完全是在浪費您的時間）

交叉字符串

題目看這里，leetcode第九十七題，hard難度：
https://leetcode.com/problems/interleaving-string/

強烈建議讀者自己先做（不過真的會有讀者嗎，笑），有任何問題歡迎在評論區(qū)討論，up看到了會及時回復。做完了歡迎在評論區(qū)打卡～

解析

首先huahua list上的下一題其實是44 wildcard matching。但是這道題和day1的題完全是一個套路，甚至還要更簡單（好像可以秒殺吧），所以為了不擺爛，我們直接略過，看下一題，也就是今天要做的交叉字符串。那么我們這里首先從未優(yōu)化的方法開始，這次一共有三個不同的答案：

1. 初次嘗試

首先是三維動態(tài)規(guī)劃矩陣。這個比我們常用的二維矩陣還多一維，就讓人感覺比較有挑戰(zhàn)性。其實基本技巧還是一樣的。所以說，刷題首先要弄清楚的事情就是不要背題。你覺得面試官有二維的矩陣不考非要考三維的矩陣是為什么？當然是知道你這個小天才早就把二維矩陣動態(tài)規(guī)劃背的滾瓜爛熟。算法面試的本質(zhì)是兩個人溝通并且解決問題，在這個過程中面試官要看到你真的動腦才行。這堆題變得越來越奇怪就是為了動腦這兩個字。背題算什么本事？面試時拿到題什么也不問，悶頭刷刷寫出最優(yōu)解，那肯定就是直接被領出去的那個。刷題的時候也要開動腦筋，長此以往才能培養(yǎng)出解題能力。

好，那么言歸正傳，這道問題的主要思路是利用一個三維矩陣來表達三個字符串之間的關系，每個維度代表一個字符串。我們的目標是判斷s1和s2是否能交錯組成s3，我們可以將這個大問題轉化為一系列子問題的求解。具體來說，我們可以取s1和s2的各一個子串，看它們能否交錯組成s3的對應部分。如果能，那么s3這一部分的最后一個字符必須是這個s1或s2子串的最后一個字符。我們通過這種方式，不斷對s1和s2取子串，判斷是否能交錯組成s3。同時，我們還需要處理邊界條件，這個時候就需要對s1，s2和s3分別進行單獨匹配，以初始化我們的動態(tài)規(guī)劃矩陣。通過這樣的方式，我們就能逐步填滿這個三維矩陣，最終根據(jù)矩陣的最后一位來判斷s1和s2是否能交錯組成s3。

那么這里的問題是啥呢？總而言之不通過，因為memory用的太多。三維矩陣還是太大，面試官會讓你優(yōu)化一下空間，這也就有了第二個答案：

2. 空間優(yōu)化

在動態(tài)規(guī)劃中，有一個常用的技巧叫做滾動數(shù)組。它的作用是減少我們需要保存的狀態(tài)數(shù)量，從而降低空間復雜度。

在這個問題里，我們觀察到狀態(tài)轉移方程中，第k步的狀態(tài)只依賴于第k-1步的狀態(tài)，也就是說我們在求解第k步的狀態(tài)時，并不需要知道第k-2步及以前的狀態(tài)。這就意味著我們并不需要把所有的狀態(tài)都保存下來，而只需要保存當前步和上一步的狀態(tài)就可以了，這就是滾動數(shù)組的思想。

但是這里有個小技巧，就是在更新第k步的狀態(tài)時，我們必須確保第k-1步的狀態(tài)不會被覆蓋。因此，在循環(huán)遍歷時，我們采用了從后向前的方式，也就是for循環(huán)的reverse函數(shù)的作用。這樣可以保證在計算當前狀態(tài)時，我們用到的上一步的狀態(tài)是準確的，沒有被錯誤地更新過。

好，現(xiàn)在新的答案還是不通過，因為耗費了太多時間。面試官繼續(xù)follow up。那么，是時候展示最終版本了。

3. 時間優(yōu)化

這個優(yōu)化技巧并沒有很強的通用性，但是它是基于一個很重要的觀察。在嘗試使用s1和s2的子串來組成s3的過程中，s1和s2的子串長度之和必然等于我們想要形成的s3子串的長度。因此，我們不需要單獨地遍歷s3，我們只需要保證s1和s2的子串長度之和等于我們要匹配的s3子串的長度。這個觀察可以幫助我們減少一次不必要的循環(huán)遍歷，因此也可以看作是一種剪枝策略。這種策略有時在動態(tài)規(guī)劃的優(yōu)化中非常有效，通過減少狀態(tài)空間或者優(yōu)化狀態(tài)轉移的計算，可以使解決問題的效率大大提高。

好，那么這就是我們的最終算法。如果甚至有讀者看到這里，那么恭喜你，你獲得了【鬃獅的小紅花】*1，這真是值得慶賀的一件事，不論你或我。所以這里推薦一首好聽的歌曲，來自安婧_Tiffany的外面的世界！

思考樂園

你可能會疑惑，為什么第三種解法不用reverse函數(shù)。是啊，怎么會事呢？這就是今天留給勤奮的你的思考問題，請盡情開動大腦吧～

教材鏈接

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