求两个字符串的最长公共子序列——Java实现

要求：给定字符串1和字符串2，要求找出两个字符串的最长公共子序列。例如，字符串1=“helloworld”，字符串2=“hwewegallgeo”,那么两者的最长公共子序列为“hello”

思路：参见：http://www.cnblogs.com/zhangchaoyang/articles/2012070.html

使用一个二维数组datas保存中间结果；使用另外一个二维数组index保存路径，用于最后查找最长公共子序列所包含的字符。

Java代码如下：

public class Solution{

// 求解两个字符号的最长公共子串
public static String maxSubseq(String strOne, String strTwo){
// 参数检查
if(strOne==null || strTwo == null){
return null;
}
if(strOne.equals("") || strTwo.equals("")){
return null;
}
// 矩阵的横向长度
int len1 = strOne.length();
// 矩阵的纵向长度
int len2 = strTwo.length();
// 二维数组用来保存中间结果
int[][] datas = new int[len1+1][len2+1];
// 使用另外一个二维数组作为标记数组，用来保存从前一步到这一步的路径
String[][] index = new String[len1+1][len2+1];
// 填充二维数组
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
int leftTop = datas[i-1][j-1];
int top = datas[i-1][j];
int left = datas[i][j-1];
if(strOne.charAt(i-1) == strTwo.charAt(j-1)){
leftTop ++;
}
int maxTemp = Math.max(leftTop, top); 
datas[i][j] = Math.max(maxTemp, left);
// 填写标记数组
if(datas[i][j] == leftTop){
index[i][j] = "leftTop";
} else if(datas[i][j]==left){
index[i][j] = "left";
} else{
index[i][j] = "top";
}
}
}
StringBuilder sBuilder = new StringBuilder();
// 从二维矩阵的最后一个元素向前查找结果，当（左上， 左， 上）数字相同时，查找顺序：左上-> 左 -> 上
int maxLen = datas[len1][len2];
System.out.println("LCS长度为:" + maxLen);
int i= len1;
int j = len2;
String indexStr = "";
char currentCh = ' ';
int currentLen = 0;
while(i>0 && j>0){
currentLen = datas[i][j];
currentCh = strOne.charAt(i-1);
indexStr = index[i][j];
if(indexStr.equals("leftTop")){
i--;
j--;
} else if(indexStr.equals("left")){
j--;
} else{
i--;
}
if(currentLen > datas[i][j]){
sBuilder.insert(0, currentCh);
}
}
return sBuilder.toString();
}

public static void main(String[] args) {
String str1 = "cbagaewagb";
String str2 = "cagewageba";
String result = Solution.maxSubseq(str1, str2);
System.out.println(result);
}
}