华为OJ之最长公共子序列
题目描述：对于两个给定的字符串，给出他们的最长公共子序列。
题目分析：
1，在之前的博文(http://www.cnblogs.com/yonguo123/p/6711360.html)中我们讨论了最长公共子串的问题，当时也指出最长公共子串其实就是最长公共子序列的一种特殊情况，那么今天我们就来一起研究一下最长公共子序列的求解；
2，最长公共子序列的定义这里不再赘述，和之前的最长公共子串一样，我们这次仍然采用动态规划和回溯的思想来解决；
3，我们假设输入为str1, str2, 首先来通过动态规划获取最大最序列的长度：
3-1，构建一个二维数组tempMatrix，维度为(str1.length + 1), (str2.length + 1);
3-2，temp的含义：str1.subString(0, i)和str2.subString(0, j)的最长公共子序列(注意理解这个数组的含义)的长度;
3-3，显然temp == 0, 当i == 0 || j == 0;
3-4，否则，当 str1.charAt(i - 1) == str2.charAt(j - 1)时，temp = temp + 1, 否则temp == max{temp, temp}(具体原因大家自己思考一下，可以从新加入的两个尾字符是否会出现在新的LCS中来思考);
4，已经构建好了tempMatix矩阵，实际上tempMatrix就是LCS的长度了，而且tempMatrix也保存了必要的回溯信息，下面我们继续构建一个String[][] flagMatrix = new String, 规则如下：
可能会有同学对这个左上，上，左的取值有疑问，请看下面这张回溯图：
实际上回溯时具体的方向与我们对于坐标的选取是有关系的，所以大家在写代码之前，应该先把坐标方向规定好。之后的工作就是利用flagMatrix来逐步回溯，详细的实现细节见代码。
5，如果还有其它更好的想法，欢迎大家与我交流^-^
具体代码(Java实现)：
import java.util.Scanner;
public class LCSequence {
public static void main(String[] args) {
String[] paras = getInput();
System.out.println(getLongestSubsequence(paras, paras));
}
public static String[] getInput() {
Scanner reader = new Scanner(System.in);
String[] paras = new String;
paras = reader.nextLine();
paras = reader.nextLine();
reader.close();
return paras;
}
public static String[][] getGenerationMatirx(String str1, String str2) {
int[][] temp = new int;
String[][] flag = new String;
for (int i = 0; i <= str1.length(); i ++) {
temp = 0;
}
for (int i = 0; i <= str2.length(); i ++) {
temp = 0;
}
//迭代获取最长公共子序列的生成矩阵
for (int i = 1; i <= str1.length(); i ++) {
for (int j = 1; j <= str2.length(); j ++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
temp = temp + 1;
flag = "left_up";
} else {
if (temp >= temp) {
temp = temp;
flag = "up";
} else {
temp = temp;
flag = "left";
}
}
}
}
return flag;
}
public static String getLongestSubsequence(String str1, String str2) {
String[][] flagMatrix = getGenerationMatirx(str1, str2);
String tempString = "";
for (int i = str1.length(), j = str2.length(); i > 0 && j > 0;) {
if (flagMatrix.equals("left_up")) {
tempString += str1.charAt(i - 1);
i --;
j --;
} else if (flagMatrix.equals("left")) {
j --;
} else {
i --;
}
}
return new StringBuffer(tempString).reverse().toString();
}
}
运行结果：
这里需要注意一点，因为LCS可能不止一个，所以对于flagMatrix的赋值其实不止一种情况，代码34行中大于或者大于等于都可以，但是可能会输出不同的结果。
页:
[1]