?

這里我們考慮用 s1和 s2的某個(gè)前綴是否能形成 s3?的一個(gè)前綴。

這個(gè)方法的前提建立于：判斷一個(gè) s3的前綴（用下標(biāo) k表示），能否用 s1和 s2?的前綴（下標(biāo)分別為 i和 j），僅僅依賴于 s1 前 i個(gè)字符和 s2?前 j個(gè)字符，而與后面的字符無關(guān)。

為了實(shí)現(xiàn)這個(gè)算法， 我們將使用一個(gè) 2D 的布爾數(shù)組 dp?。dp[i][j]表示用 s1的前 i和 s2的前 j個(gè)字符，總共 i+j個(gè)字符，是否交錯(cuò)構(gòu)成 s3的前綴。為了求出 dp[i][j]?，我們需要考慮 兩?種情況：

s1的第 i 個(gè)字符和 s2?的第 j 個(gè)字符都不能匹配 s3的第 k?個(gè)字符，其中 k=i + j?。這種情況下，s1和 s2的前綴無法交錯(cuò)形成 s3長(zhǎng)度為 k 的前綴。因此，我們讓 dp[i][j]為 False。

s1的第 i 個(gè)字符或者 s2的第 j 個(gè)字符可以匹配 s3的第 k個(gè)字符，其中 k=i+j?。假設(shè)匹配的字符是 x?且與 s1的第 i?個(gè)字符匹配，我們就需要把 x放在已經(jīng)形成的交錯(cuò)字符串的最后一個(gè)位置。此時(shí)，為了我們必須確保 s1的前 (i-1)個(gè)字符和 s2的前 j 個(gè)字符能形成 s3的一個(gè)前綴。類似的，如果我們將 s2的第 j個(gè)字符與 s3的第 k 個(gè)字符匹配，我們需要確保 s1的前 i 個(gè)字符和 s2的前 (j-1)?個(gè)字符能形成 s3的一個(gè)前綴，我們就讓 dp[i][j]為True 。

?

public class Solution {public bool IsInterleave(string s1, string s2, string s3){if((s1.Length + s2.Length) != s3.Length)return false;bool[,] dp = new bool[s1.Length + 1, s2.Length + 1];for(int i = 0; i <= s1.Length; i++){for(int j = 0; j <= s2.Length; j++){if(i == 0 && j == 0)dp[i, j] = true;else if(i == 0)dp[i, j] = dp[i, j - 1] && s2[j - 1] == s3[i+ j - 1];else if(j == 0)dp[i, j] = dp[i - 1, j] && s1[i - 1] == s3[i+ j - 1];elsedp[i, j] = (dp[i - 1, j] && s1[i - 1] == s3[i+ j - 1]) || dp[i, j - 1] && s2[j - 1] == s3[i+ j - 1];}}return dp[s1.Length, s2.Length];} }

復(fù)雜度分析

時(shí)間復(fù)雜度：O(m \cdot n)O(m?n) 。計(jì)算 dpdp 數(shù)組需要 m*nm?n 的時(shí)間。

空間復(fù)雜度：O(m \cdot n)O(m?n)。2 維的 dpdp 數(shù)組需要 (m+1)*(n+1)(m+1)?(n+1) 的空間。 mm 和 nn 分別是 s1s1 和 s2s2 字符串的長(zhǎng)度。

優(yōu)化：使用一維動(dòng)態(tài)規(guī)劃

這種方法與前一種方法基本一致，除了我們僅使用一維 dp數(shù)組去儲(chǔ)存前綴結(jié)果。我們利用 dp[i-1]的結(jié)果和 dp[i]之前的結(jié)果來計(jì)算 dp[i]，即滾動(dòng)數(shù)組。

public bool IsInterleave(string s1, string s2, string s3){if((s1.Length + s2.Length) != s3.Length)return false;bool[] dp = new bool[s2.Length + 1];for(int i = 0; i <= s1.Length; i++){for(int j = 0; j <= s2.Length; j++){if(i==0 && j == 0)dp[j] = true;else if(i == 0)dp[j] = dp[j - 1] && s2[j - 1] == s3[i+ j - 1];else if(j == 0)dp[j] = dp[j] && s1[i - 1] == s3[i+ j - 1];elsedp[j] = (dp[j] && s1[i - 1] == s3[i+ j - 1]) || dp[j - 1] && s2[j - 1] == s3[i+ j - 1];}}return dp[s2.Length];}

?

復(fù)雜度分析

時(shí)間復(fù)雜度：O(m?n)；長(zhǎng)度為 n 的 dp數(shù)組需要被填充 m 次。

空間復(fù)雜度：O(n)；n是字符串 s1的長(zhǎng)度

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的LeetCode 97: 交错字符串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。