廢話不多說，喊一句號子鼓勵自己：程序員永不失業(yè)，程序員走向架構(gòu)！本篇Blog的主題是【】，使用【】這個基本的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，這個高頻題的站點是：CodeTop，篩選條件為：目標公司+最近一年+出現(xiàn)頻率排序，由高到低的去?？蚑OP101去找，只有兩個地方都出現(xiàn)過才做這道題（CodeTop本身匯聚了LeetCode的來源），確保刷的題都是高頻要面試考的題。
名曲目標題后，附上題目鏈接，后期可以依據(jù)解題思路反復(fù)快速練習(xí)，題目按照題干的基本數(shù)據(jù)結(jié)構(gòu)分類，且每個分類的第一篇必定是對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的介紹。
最長重復(fù)子數(shù)組【MID】
線性DP問題再搞一道，最長重復(fù)子數(shù)組
題干
解題思路
原題解地址：A 、B數(shù)組各抽出一個前綴數(shù)組，單看它們的末尾項：
- 如果它們倆不一樣，則公共子數(shù)組肯定不包括它們倆。
- 如果它們倆一樣，則要考慮它們倆前面的子數(shù)組「能為它們倆提供多大的公共長度」。
繼續(xù)向前遞推的：
- 如果它們倆的前綴數(shù)組的「末尾項」不相同，由于子數(shù)組的連續(xù)性，前綴數(shù)組不能為它們倆提供公共長度
- 如果它們倆的前綴數(shù)組的「末尾項」相同，則可以為它們倆提供公共長度：至于提供多長的公共長度？這又取決于前綴數(shù)組的末尾項是否相同……
存在重復(fù)子問題和遞推的方法，可以用動態(tài)規(guī)劃解決?；氐筋}目，A 、B數(shù)組各抽出一個前綴子數(shù)組，單看它們的末尾項
- 如果它們倆不一樣——以它們倆為末尾項形成的公共子數(shù)組的長度為0：
dp[i][j] = 0 - 如果它們倆一樣，以它們倆為末尾項的公共子數(shù)組，長度保底為1——dp[i][j]至少為 1，要考慮它們倆的前綴數(shù)組——dp[i-1][j-1]能為它們倆提供多大的公共長度
繼續(xù)向前遞推：
- 如果它們倆的前綴數(shù)組的「末尾項」不相同，前綴數(shù)組提供的公共長度為 0——
dp[i-1][j-1] = 0，以它們倆為末尾項的公共子數(shù)組的長度——dp[i][j] = 1 - 如果它們倆的前綴數(shù)組的「末尾項」相同，前綴部分能提供的公共長度——
dp[i-1][j-1]，它至少為 1，以它們倆為末尾項的公共子數(shù)組的長度dp[i][j] = dp[i-1][j-1] + 1
題目求：最長公共子數(shù)組的長度。不同的公共子數(shù)組的末尾項不一樣。我們考察不同末尾項的公共子數(shù)組，找出最長的那個。
1 定義狀態(tài)（定義子問題）
我們定義dp[i][j]標識 ：長度為i，末尾項為A[i-1]的子數(shù)組，與長度為j，末尾項為B[j-1]的子數(shù)組，二者的最大公共后綴子數(shù)組長度
2 定義狀態(tài)轉(zhuǎn)移方程
dp[i][j] ：長度為i，末尾項為A[i-1]的子數(shù)組，與長度為j，末尾項為B[j-1]的子數(shù)組，二者的最大公共后綴子數(shù)組長度。
- 如果
A[i-1] != B[j-1]， 有dp[i][j] = 0 - 如果
A[i-1] == B[j-1]， 有dp[i][j] = dp[i-1][j-1] + 1
3 初始化狀態(tài)
為了不判斷邊界條件，我們給DP Table補0，所以base case：如果i==0||j==0，則二者沒有公共部分，dp[i][j]=0
4 求解方向
這里采用自底向上，從最小的狀態(tài)開始求解
5 找到最終解
最長公共子數(shù)組以哪一項為末尾項都有可能，求出每個 dp[i][j]，找出最大值。
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：數(shù)組
輔助數(shù)據(jù)結(jié)構(gòu)：無
算法：動態(tài)規(guī)劃
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param number int整型
* @return int整型
*/
public int findLength(int[] nums1, int[] nums2) {
// 1 入?yún)惓Ｐｒ?/span>
if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
return 0;
}
// 2 定義dp數(shù)組，dp[i][j] 表示以nums1中以i-1結(jié)尾的元素與nums2中以j-1結(jié)尾的元素最長重復(fù)子數(shù)組
int rows = nums1.length;
int cols = nums2.length;
// base case dp[0][0]=0,初始化第一行第一列為0
int[][] dp = new int[rows + 1][cols + 1];
// 3 狀態(tài)轉(zhuǎn)移方程
int ans = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
// 如果以i-1,j-1為結(jié)尾的元素相等，則至少重復(fù)子數(shù)組長度+1，并比較大小
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
// 設(shè)置值的過程中更新最大值
ans = Math.max(ans, dp[i][j]);
} else {
// 如果以i-1,j-1為結(jié)尾的元素不相等，則無重復(fù)子數(shù)組，長度歸0
dp[i][j] = 0;
}
}
}
return ans;
}
}
復(fù)雜度分析
時間復(fù)雜度：O(N*M)，這里 N 是數(shù)組的長度，我們寫了兩個 for 循環(huán)，每個 for 循環(huán)的時間復(fù)雜度都是線性的；
空間復(fù)雜度：O(N*M)，DP數(shù)組是二維數(shù)組
最長公共子串【MID】
首先來一道最長公共子串，難度還沒有升級，公共字符是連續(xù)的即可
題干
解題思路
求兩個數(shù)組或者字符串的最長公共子序列問題，肯定是要用動態(tài)規(guī)劃的。
- 首先，區(qū)分兩個概念：子序列可以是不連續(xù)的；子數(shù)組（子字符串）需要是連續(xù)的；
- 另外，單個數(shù)組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃
dp[i]定義為nums[0:i]中想要求的結(jié)果；當兩個數(shù)組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃定義成兩維的dp[i][j]，其含義是在A[0:i]與B[0:j]之間匹配得到的想要的結(jié)果。
1. 狀態(tài)定義
對于本題而言，可以定義 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。 （注：text1[0:i-1] 表示的是 text1 的 第 0 個元素到第 i - 1 個元素，兩端都包含） 之所以 dp[i][j] 的定義不是 text1[0:i] 和 text[0:j] ，是為了方便當 i = 0 或者 j = 0 的時候，dp[i][j]表示空字符串和另外一個字符串的匹配，這樣 dp[i][j] 可以初始化為空字符串
2. 狀態(tài)轉(zhuǎn)移方程
知道狀態(tài)定義之后，開始寫狀態(tài)轉(zhuǎn)移方程。
- 當
text1[i - 1] == text2[j - 1]時，說明兩個子字符串的最后一位相等，所以最長公共子串長度又增加了 1，所以dp[i][j] = dp[i - 1][j - 1] + text1[i]； - 當
text1[i - 1] != text2[j - 1]時，說明兩個子字符串的最后一位不相等，所以不夠成公共子串，不滿足條件
綜上狀態(tài)轉(zhuǎn)移方程為：
-
dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1), 當text1[i?1]==text2[j?1]
當然我們還需要當前最新下標來輔助記錄子串最新的更新位置
3. 狀態(tài)的初始化
初始化就是要看當 i = 0 與 j = 0 時， dp[i][j] 應(yīng)該取值為多少。
- 當 i = 0 時，
dp[0][j]表示的是 text1中取空字符串 跟 text2的最長公共子序列，結(jié)果肯定為 空字符串. - 當 j = 0 時，
dp[i][0]表示的是 text2中取空字符串 跟 text1的最長公共子序列，結(jié)果肯定為 空字符串.
綜上，當 i = 0 或者 j = 0 時，dp[i][j] 初始化為 空字符串.
4. 遍歷方向與范圍
由于 dp[i][j] 依賴于 dp[i - 1][j - 1] ,，所以 i和 j的遍歷順序肯定是從小到大（自底向上）的。 另外，由于當 i和 j 取值為 0 的時候，dp[i][j] = 0，而 dp 數(shù)組本身初始化就是為 空字符串，所以，直接讓 i 和 j 從 1 開始遍歷。遍歷的結(jié)束應(yīng)該是字符串的長度為 len(text1)和 len(text2)。
5. 最終返回結(jié)果
由于 dp[i][j] 的含義是 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。我們最終希望求的是 text1 和 text2 的最長公共子序列。所以需要返回的結(jié)果是 i = len(text1) 并且 j = len(text2) 時的 dp[len(text1)][len(text2)]。
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：字符串
輔助數(shù)據(jù)結(jié)構(gòu)：無
算法：動態(tài)規(guī)劃
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String LCS (String str1, String str2) {
// 入?yún)l件判斷
if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 1) {
return null;
}
// 1 初始化狀態(tài)
int ls1 = str1.length();
int ls2 = str2.length();
// dp表示范圍為0-ls1的str1與0-ls2的str2的最長公共子串長度
int[][] dp = new int[ls1 + 1][ls2 + 1];
int max = 0;
int latestIndex = 0;
// 2 遍歷（自底向上）
for (int i = 1; i <= ls1; i++) {
for (int j = 1; j <= ls2; j++) {
// 狀態(tài)轉(zhuǎn)移方程
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
// 更新子串最大長度以及當前子串下標
if (dp[i][j] > max) {
max = dp[i][j];
// 公共子串不包含latestIndex位置
latestIndex = i;
}
}
}
}
// 上述循環(huán)i從1開始，這里subString右側(cè)為開區(qū)間，剛好適用
return str1.substring(latestIndex - max, latestIndex);
}
}
復(fù)雜度分析
時間復(fù)雜度：O(n^2 )，構(gòu)造輔助數(shù)組dp與b，兩層循環(huán)，遞歸是有方向的遞歸，因此只是相當于遍歷了二維數(shù)組
空間復(fù)雜度：O(n^2 )，輔助二維數(shù)組dp與遞歸棧的空間最大為O(n^2 )
最長公共子序列【MID】
難度升級，明確下什么是公共子序列。一個字符串的子序列是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
例如，ace是 abcde的子序列，但 aec不是 abcde 的子序列
題干
解題思路
求兩個數(shù)組或者字符串的最長公共子序列問題，肯定是要用動態(tài)規(guī)劃的。
- 首先，區(qū)分兩個概念：子序列可以是不連續(xù)的；子數(shù)組（子字符串）需要是連續(xù)的；
- 另外，單個數(shù)組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃
dp[i]定義為nums[0:i]中想要求的結(jié)果；當兩個數(shù)組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃定義成兩維的dp[i][j]，其含義是在A[0:i]與B[0:j]之間匹配得到的想要的結(jié)果。
1. 狀態(tài)定義
對于本題而言，可以定義 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。 （注：text1[0:i-1] 表示的是 text1 的 第 0 個元素到第 i - 1 個元素，兩端都包含） 之所以 dp[i][j] 的定義不是 text1[0:i] 和 text[0:j] ，是為了方便當 i = 0 或者 j = 0 的時候，dp[i][j]表示空字符串和另外一個字符串的匹配，這樣 dp[i][j] 可以初始化為空字符串
2. 狀態(tài)轉(zhuǎn)移方程
知道狀態(tài)定義之后，開始寫狀態(tài)轉(zhuǎn)移方程。
- 當
text1[i - 1] == text2[j - 1]時，說明兩個子字符串的最后一位相等，所以最長公共子序列又增加了 1，所以dp[i][j] = dp[i - 1][j - 1] + text1[i]；舉個例子，比如對于 ac 和 bc 而言，他們的最長公共子序列的長度等于 a 和 b 的最長公共子序列長度 0 + text[1] = c。 - 當
text1[i - 1] != text2[j - 1]時，說明兩個子字符串的最后一位不相等，那么此時的狀態(tài)dp[i][j]應(yīng)該是dp[i - 1][j]和dp[i][j - 1]的最大值。舉個例子，比如對于 ace 和 bc 而言，他們的最長公共子序列等于 ① ace 和 b 的最長公共子序列:空字符串的長度0 與 ② ac 和 bc 的最長公共子序列c長度1 的最大值，即 1，所以選擇長度大的
綜上狀態(tài)轉(zhuǎn)移方程為：
-
dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1), 當text1[i?1]==text2[j?1] -
dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];, 當text1[i?1]!=text2[j?1]
3. 狀態(tài)的初始化
初始化就是要看當 i = 0 與 j = 0 時， dp[i][j] 應(yīng)該取值為多少。
- 當 i = 0 時，
dp[0][j]表示的是 text1中取空字符串 跟 text2的最長公共子序列，結(jié)果肯定為 空字符串. - 當 j = 0 時，
dp[i][0]表示的是 text2中取空字符串 跟 text1的最長公共子序列，結(jié)果肯定為 空字符串.
綜上，當 i = 0 或者 j = 0 時，dp[i][j] 初始化為 空字符串.
4. 遍歷方向與范圍
由于 dp[i][j] 依賴于 dp[i - 1][j - 1] ,，所以 i和 j的遍歷順序肯定是從小到大（自底向上）的。 另外，由于當 i和 j 取值為 0 的時候，dp[i][j] = 0，而 dp 數(shù)組本身初始化就是為 空字符串，所以，直接讓 i 和 j 從 1 開始遍歷。遍歷的結(jié)束應(yīng)該是字符串的長度為 len(text1)和 len(text2)。
5. 最終返回結(jié)果
由于 dp[i][j] 的含義是 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。我們最終希望求的是 text1 和 text2 的最長公共子序列。所以需要返回的結(jié)果是 i = len(text1) 并且 j = len(text2) 時的 dp[len(text1)][len(text2)]。
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：字符串
輔助數(shù)據(jù)結(jié)構(gòu)：無
算法：動態(tài)規(guī)劃
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// 0 入?yún)⑿ｒ?/span>
if (s1 == null || s1.length() == 0 || s2 == null ||
s2.length() == 0) return "-1";
// 1 狀態(tài)定義及初始化
int ls1 = s1.length();
int ls2 = s2.length();
// 長度為ls1和長度為ls2的最長公共子序列是dp
String[][] dp = new String[ls1 + 1][ls2 + 1];
// 2 初始化狀態(tài)值，當初始化狀態(tài)時，公共子序列為空字符串
for (int i = 0; i <= ls1; i++) {
// j為0表示一個長度不為0的s1和一個長度永遠為0的字符串公共子序列一定是空字符串
dp[i][0] = "";
}
for (int j = 0; j <= ls2; j++) {
// i為0表示一個長度不為0的s1和一個長度永遠為0的字符串公共子序列一定是空字符串
dp[0][j] = "";
}
// 3 自底向上遍歷
for (int i = 1; i <= ls1; i++) {
for (int j = 1; j <= ls2; j++) {
// 4 狀態(tài)轉(zhuǎn)移方程
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// 如果s1和s2的字符相等，dp[1][1]表示dp[0][0]+a=a(自底向上)
dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
} else {
// 如果s1和s2的字符不相等，取dp[i - 1][j]和dp[i][j - 1]較長的字符作為dp[i][j]
dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] :
dp[i][j - 1];
}
}
}
// 5 返回的是兩個完整s1和s2的公共子序列
return dp[ls1][ls2] == "" ? "-1" : dp[ls1][ls2];
}
}
復(fù)雜度分析
時間復(fù)雜度：O(n^2 )，構(gòu)造輔助數(shù)組dp與b，兩層循環(huán)，遞歸是有方向的遞歸，因此只是相當于遍歷了二維數(shù)組
空間復(fù)雜度：O(n^2 )，輔助二維數(shù)組dp與遞歸棧的空間最大為O(n^2 )
編輯距離【HARD】
終于又來到一道看了很久的高頻題目這里
題干
搞定了一系列的簡單題，來個編輯距離練練手
解題思路
原題解地址，解決兩個字符串的動態(tài)規(guī)劃問題，一般都是用兩個指針 i, j 分別指向兩個字符串的最后，然后一步步往前移動，縮小問題的規(guī)模
設(shè)兩個字符串分別為 rad 和 apple，為了把 s1 變成 s2，算法會這樣進行
暴力遞歸
base case 是 i 走完 s1 或 j 走完 s2，可以直接返回另一個字符串剩下的長度。對于每對兒字符 s1[i] 和 s2[j]，可以有四種操作：
if s1[i] == s2[j]:
啥都別做（skip）
i, j 同時向前移動
else:
三選一：
插入（insert）
刪除（delete）
替換（replace）
有這個框架，問題就已經(jīng)解決了。讀者也許會問，這個「三選一」到底該怎么選擇呢？很簡單，全試一遍，哪個操作最后得到的編輯距離最小，就選誰
int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
// i，j 初始化指向最后一個索引
return dp(s1, m - 1, s2, n - 1);
}
// 定義：返回 s1[0..i] 和 s2[0..j] 的最小編輯距離
int dp(String s1, int i, String s2, int j) {
// base case
if (i == -1) return j + 1;
if (j == -1) return i + 1;
if (s1.charAt(i) == s2.charAt(j)) {
return dp(s1, i - 1, s2, j - 1); // 啥都不做
}
return min(
dp(s1, i, s2, j - 1) + 1, // 插入
dp(s1, i - 1, s2, j) + 1, // 刪除
dp(s1, i - 1, s2, j - 1) + 1 // 替換
);
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
情況一：什么都不做
if s1[i] == s2[j]:
return dp(s1, i - 1, s2, j - 1); # 啥都不做
# 解釋：
# 本來就相等，不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小編輯距離等于
# s1[0..i-1] 和 s2[0..j-1] 的最小編輯距離
# 也就是說 dp(i, j) 等于 dp(i-1, j-1)
如果 s1[i] != s2[j]，就要對三個操作遞歸了
情況二：插入操作
dp(s1, i, s2, j - 1) + 1, # 插入
# 解釋：
# 我直接在 s1[i] 插入一個和 s2[j] 一樣的字符
# 那么 s2[j] 就被匹配了，前移 j，繼續(xù)跟 i 對比
# 別忘了操作數(shù)加一
插入操作
情況三：刪除操作
dp(s1, i - 1, s2, j) + 1, # 刪除
# 解釋：
# 我直接把 s[i] 這個字符刪掉
# 前移 i，繼續(xù)跟 j 對比
# 操作數(shù)加一
情況四：替換操作
dp(s1, i - 1, s2, j - 1) + 1 # 替換
# 解釋：
# 我直接把 s1[i] 替換成 s2[j]，這樣它倆就匹配了
# 同時前移 i，j 繼續(xù)對比
# 操作數(shù)加一
a字符被替換為p字符
int dp(i, j) {
dp(i - 1, j - 1); // #1
dp(i, j - 1); // #2
dp(i - 1, j); // #3
}
對于子問題 dp(i-1, j-1)，如何通過原問題 dp(i, j) 得到呢？有不止一條路徑，比如 dp(i, j) -> #1 和 dp(i, j) -> #2 -> #3。一旦發(fā)現(xiàn)一條重復(fù)路徑，就說明存在巨量重復(fù)路徑，也就是重疊子問題
動態(tài)規(guī)劃
接下來用DP table來優(yōu)化一下，降低重復(fù)子問題，首先明確 dp 數(shù)組的含義，dp 數(shù)組是一個二維數(shù)組，長這樣
有了之前遞歸解法的鋪墊，應(yīng)該很容易理解。dp[..][0] 和 dp[0][..] 對應(yīng) base case，dp[i][j] 的含義和之前的 dp 函數(shù)類似
-
替換操作：word1的
0~i-1位置與word2的0~j-1位置的字符都相同,只是當前位置的字符不匹配,進行替換操作后兩者變得相同dp[i-1][j-1]表示需要進行替換操作才能轉(zhuǎn)到dp[i][j]， 所以此時dp[i][j]=dp[i-1][j-1]+1(這個加1代表執(zhí)行替換操作) -
刪除操作: 若此時word1的
0~i-1位置與word2的0~j位置已經(jīng)匹配了,此時多出了word1的i位置字符,應(yīng)把它刪除掉,才能使此時word1的0~i(這個i是執(zhí)行了刪除操作后新的i)和word2的0~j位置匹配,因此此時dp[i][j]=dp[i-1][j]+1(這個加1代表執(zhí)行刪除操作) -
插入操作:若此時word1的
0~i位置只是和word2的0~j-1位置匹配，此時只需要在原來的i位置后面插入一個和word2的j位置相同的字符使得此時的word1的0~i(這個i是執(zhí)行了插入操作后新的i)和word2的0~j匹配得上,所以此時dp[i][j]=dp[i][j-1]+1(這個加1代表執(zhí)行插入操作)
有了之前遞歸解法的鋪墊，應(yīng)該很容易理解。dp[..][0] 和 dp[0][..] 對應(yīng) base case，dp[i][j] 的含義和之前的 dp 函數(shù)類似
int dp(String s1, int i, String s2, int j)
// 返回 s1[0..i] 和 s2[0..j] 的最小編輯距離
dp 函數(shù)的 base case 是 i, j 等于 -1，而數(shù)組索引至少是 0，所以 dp 數(shù)組會偏移一位
dp[i-1][j-1]
// 存儲 s1[0..i] 和 s2[0..j] 的最小編輯距離
既然 dp 數(shù)組和遞歸 dp 函數(shù)含義一樣，也就可以直接套用之前的思路寫代碼，唯一不同的是，DP table 是自底向上求解，遞歸解法是自頂向下求解
int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 定義：s1[0..i] 和 s2[0..j] 的最小編輯距離是 dp[i+1][j+1]
int[][] dp = new int[m + 1][n + 1];
// base case
for (int i = 1; i <= m; i++)
dp[i][0] = i;
for (int j = 1; j <= n; j++)
dp[0][j] = j;
// 自底向上求解
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
);
}
}
}
// 儲存著整個 s1 和 s2 的最小編輯距離
return dp[m][n];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：數(shù)組
輔助數(shù)據(jù)結(jié)構(gòu)：無
算法：動態(tài)規(guī)劃
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
// 注意類名必須為 Main, 不要有任何 package xxx 信息
class Solution
{
// 編輯距離，返回兩個字符串操作的最小距離
public int minDistance(String word1, String word2)
{
// 1 入?yún)⑿ｒ?/span>
if(word1.length() < 1 && word2.length() < 1)
{
return 0;
}
// 2 定義行列長度，word1作為豎，word2作為行
int m = word1.length();
int n = word2.length();
// 定義：s1[0..i] 和 s2[0..j] 的最小編輯距離是 dp[i+1][j+1]
int[][] dp = new int[m + 1][n + 1];
// 4 初始化base case
for(int i = 1; i <= m; i++)
{
dp[i][0] = i;
}
for(int j = 1; j <= n; j++)
{
dp[0][j] = j;
}
// 5 狀態(tài)轉(zhuǎn)移方程:自底向上求解，從頭開始比較，i=0和j=0的位置初始化為基本操作數(shù)
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if(word1.charAt(i-1) == word2.charAt(j-1))
{
dp[i][j] = dp[i - 1][j - 1];
}else
{
dp[i][j] = minCompare(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
}
}
}
return dp[m][n];
}
private int minCompare(int a, int b, int c)
{
return Math.min(a, Math.min(b, c));
}
}
文章來源：http://www.zghlxwxcb.cn/news/detail-700099.html
- 第一行，是 word1 為空，變成 word2 最少步數(shù)，就是插入操作
- 第一列，是 word2 為空，word1要變?yōu)閣ord2(也就是空)需要的最少步數(shù)，就是刪除操作
(一)、當word1[i]==word2[j]時,由于遍歷到了i和j,說明word1的0~i-1和word2的0~j-1的匹配結(jié)果已經(jīng)生成,
由于當前兩個字符相同,因此無需做任何操作,dp[i][j]=dp[i-1][j-1]
(二)、當word1[i]!=word2[j]時,可以進行的操作有3個:
① 替換操作:可能word1的0~i-1位置與word2的0~j-1位置的字符都相同,
只是當前位置的字符不匹配,進行替換操作后兩者變得相同,
所以此時dp[i][j]=dp[i-1][j-1]+1(這個加1代表執(zhí)行替換操作)
②刪除操作:若此時word1的0~i-1位置與word2的0~j位置已經(jīng)匹配了,
此時多出了word1的i位置字符,應(yīng)把它刪除掉,才能使此時word1的0~i(這個i是執(zhí)行了刪除操作后新的i)
和word2的0~j位置匹配,因此此時dp[i][j]=dp[i-1][j]+1(這個加1代表執(zhí)行刪除操作)
③插入操作:若此時word1的0~i位置只是和word2的0~j-1位置匹配,
此時只需要在原來的i位置后面插入一個和word2的j位置相同的字符使得
此時的word1的0~i(這個i是執(zhí)行了插入操作后新的i)和word2的0~j匹配得上,
所以此時dp[i][j]=dp[i][j-1]+1(這個加1代表執(zhí)行插入操作)
④由于題目所要求的是要最少的操作數(shù):所以當word1[i] != word2[j] 時,
需要在這三個操作中選取一個最小的值賦格當前的dp[i][j]
(三)總結(jié):狀態(tài)方程為:
if(word1[i] == word2[j]):
dp[i][j] = dp[i-1][j-1]
else:
min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
PS:大佬的代碼中word1.charAt(i-1)==word2.charAt(j-1)的原因是:
初始化DP Table時dp[i][0]和dp[0][j]已經(jīng)填寫完成,所以接下來填表需要從1開始,
但是字符的比較需要從0開始,因此才這樣子寫
復(fù)雜度分析
時間復(fù)雜度：O(N^2)，這里 N 是數(shù)組的長度，我們寫了兩個 for 循環(huán)，每個 for 循環(huán)的時間復(fù)雜度都是線性的；
空間復(fù)雜度：O(N)，要使用和輸入數(shù)組長度相等的狀態(tài)數(shù)組，因此空間復(fù)雜度是 O(N)。文章來源地址http://www.zghlxwxcb.cn/news/detail-700099.html
到了這里，關(guān)于【算法訓(xùn)練-字符串 三】最長公共子串、最長公共子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
