最長XX子串/數組/子序列

一、最長公共子串

　　題目描述：

　　　　字元串s=“heqlloled”，字元串p=“eolold!”。找出兩個字元串最長的共有的子字元串。　

　　輸入：

　　　　acbcbcef

　　　　abcbced

　　輸出：

　　　　5

　　　　bcbce

　　解決：

　　　　dp[i][j]表示s[0,…i]與p[0,…j]區間之間而且以i和j結尾的最長公共子串長度，狀态轉移方程：

　　　　　　(1)當s[i]==p[j]時，dp[i][j]=dp[i-1][j-1]+1;

　　　　　　(2)當s[i]!=p[j]時，dp[i][j]=0;

　　代碼如下：

二、最長公共子序列

　　　　字元串s=“heqlloled”，字元串p=“eolold!”。輸出最長公共子序列。

　　　　abcde

　　　　ace

　　　　3

　　　　dp[i][j]表示s[0,…i]與p[0,…j]的最長公共子序列長度。

　　狀态轉移方程：

　　　　(1) 當s[i]==p[j]時，dp[i][j] = dp[i-1][j-1] + 1;

　　　　(2) 當s[i]!=p[j]時，dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

三、尋找目标子串

　　題目連結：https://leetcode-cn.com/problems/implement-strstr/

　　在一個字元串中尋找是否包含目标字元串，實作這個要求并不難，周遊文本的每個字元串，如果和目标字元串的第一個比對，就把比對的字元後移一位繼續對比，直到不比對，然後将文本的指針後移一位，繼續對比即可。但是這樣的暴力比對最壞情況的時間複雜度為o（n*m），而kmp算法可以将其複雜度降低到o（n+m），減少重複對比次數。

四、最長回文子串

　　題目連結：https://leetcode-cn.com/problems/longest-palindromic-substring/

　　題目描述：給你一個字元串 ​<code>​s​</code>​，找到 ​<code>​s​</code>​ 中最長的回文子串。

　　解法1：動态規劃：對于一個子串而言，如果它是回文串，并且長度大于 22，那麼将它首尾的兩個字母去除之後，它仍然是個回文串。例如對于字元串 \textrm{``ababa''}“ababa”，如果我們已經知道 \textrm{``bab''}“bab” 是回文串，那麼 \textrm{``ababa''}“ababa” 一定是回文串，這是因為它的首尾兩個字母都是 \textrm{``a''}“a”。

　　dp[i][j]代表從i到j的子串是否為回文串，如果s[i] == s[j] 并且j - i == 1或者dp[i+1][j-1]為true，那麼dp[i][j] = true;時間複雜度和空間複雜度分别為o(n^2)和o(n^2)。

　　解法2：中心擴充算法：我們枚舉所有的「回文中心」并嘗試「擴充」，直到無法擴充為止，此時的回文串長度即為此「回文中心」下的最長回文串長度。我們對所有的長度求出最大值，即可得到最終的答案。

五、最長重複子串

　　題目連結：

　　　　https://leetcode-cn.com/problems/longest-duplicate-substring/　

　　　　給出一個字元串 s，考慮其所有重複子串（s 的連續子串，出現兩次或多次，可能會有重疊）。

　　　　傳回任何具有最長可能長度的重複子串。（如果 s 不含重複子串，那麼答案為 ""。）

　　解決：二分+字元串哈希　　

六、最長不含重複字元的子串

　　　　https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

　　　　請從字元串中找出一個最長的不包含重複字元的子字元串，計算該最長子字元串的長度。

　　解決：雙指針+滑動視窗

七、最長遞增子序列

　　　　https://leetcode-cn.com/problems/longest-increasing-subsequence/

　　題目描述：　　

　　　　給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

　　　　子序列是由數組派生而來的序列，删除（或不删除）數組中的元素而不改變其餘元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

　　解決：動态規劃

作者：mr-xxx，轉載請注明原文連結​