問題解讀
最長公共子序列問題褥紫，就是找出兩個字符串中，存在的最長的
子序列
什么是子序列呢冬筒？
子序列不同于公共子串恐锣，子串是每個字符連續(xù)的，子序列不一定要連續(xù)舞痰，見下例 [example]
[example]: 比如 mStringA = "abc11google11111111", mStringB = "1111111141615" 這兩個字符串
那么土榴，mStringA 和 mStringB 的最長公共子序列就是 1111111111
如何求解
我們對于問題進行白話講解，假如現(xiàn)在有兩個字符串响牛，并且有兩個指針玷禽，這每個指針，各自指向這兩個字符串娃善，我們把這兩個指針設(shè)置為 i 和 j论衍，即，i 指向 mStringA 的某個字符聚磺，j 指向 mStringB 的某個字符坯台，那么，此時的狀態(tài)方程為 f(i, j)瘫寝，表示 i 指向 mStringA 的某個字符和 j 指向 mStringB 的某個字符的情況
- 當(dāng)兩個指針指向的字符相等時蜒蕾，那么代表這是一個成功的狀態(tài)，此時焕阿，狀態(tài)記為
f(i + 1, j + 1) + 1咪啡，表示 i 和 j 兩個指針可以同時向右方移動- 當(dāng)兩個指針指向的字符不相等的試試，那么代表這是一個待完成的狀態(tài)暮屡，此時撤摸，狀態(tài)記為
f(i + 1, j)和f(i, j + 1)
Talk is cheap, show me code ~~~
package com.company;
import org.junit.Test;
public class LongestCommonSequence {
// 用來存儲匹配過程中存取的記錄
public StringBuilder sb = new StringBuilder();
/*
* 獲得最長公共子序列的方法
* 傳入兩個參數(shù)，即為需要處理的字符串
* 核心實現(xiàn)方法在 longestCommonSequence(...)
*/
public String getLongestCommonSequence(String mStringA, String mStringB) {
// 1. 拿到最長公共子序列的長度
int strLength = longestCommonSequence(0, mStringA, 0, mStringB);
// 2. 將 StringBuilder 轉(zhuǎn)為 String 類
String mString = new String(sb);
// 3. 對記錄進行裁剪褒纲，最后的 strLength 個字符准夷，是最終的結(jié)果
return mString.substring(
strLength - longestCommonSequence(0, mStringA, 0, mStringB),
strLength);
}
// 最長公共子序列的實現(xiàn)方法
public int longestCommonSequence(int i, String mStringA, int j, String mStringB) {
// 1. 邊界條件判斷，當(dāng)指針到頭的時候莺掠，返回 0
if (i == mStringA.length() || j == mStringB.length()) {
return 0;
}
// 2. 當(dāng)兩個指針指向的字符相等的時候衫嵌，這是狀態(tài)方程為：f(i + 1, j + 1) + 1
if (mStringA.charAt(i) == mStringB.charAt(j)) {
sb.append(mStringA.charAt(i));
return longestCommonSequence(i + 1, mStringA, j + 1, mStringB) + 1;
} else { // 3. 當(dāng)兩個指針指向的字符不相等的時候，這是狀態(tài)方程為：f(i + 1, j) 或者 f(i, j + 1)
return Math.max(longestCommonSequence(i + 1, mStringA, j, mStringB),
longestCommonSequence(i, mStringA, j + 1, mStringB));
}
}
// 測試方法
@Test
public void test() {
// 1111111111
System.out.println(
getLongestCommonSequence("abc11google11111111",
"1111111141615")
);
}
}
