求两个字符串的最长公共子序列——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);
	}
}