华为OJ之最长公共子序列

beebe_3

　　题目描述：
　　对于两个给定的字符串，给出他们的最长公共子序列。
　　题目分析：
　　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[j]的含义：str1.subString(0, i)和str2.subString(0, j)的最长公共子序列(注意理解这个数组的含义)的长度;
　　3-3，显然temp[j] == 0, 当i == 0 || j == 0;
　　3-4，否则，当 str1.charAt(i - 1) == str2.charAt(j - 1)时，temp[j] = temp[i - 1][j - 1] + 1, 否则temp[j] == max{temp[i, j - 1], temp[i - 1, j]}(具体原因大家自己思考一下，可以从新加入的两个尾字符是否会出现在新的LCS中来思考);
　　4，已经构建好了tempMatix矩阵，实际上tempMatrix[str1.length][str2.length]就是LCS的长度了，而且tempMatrix也保存了必要的回溯信息，下面我们继续构建一个String[][] flagMatrix = new String[str1.length][str2.length], 规则如下：

　　可能会有同学对这个左上，上，左的取值有疑问，请看下面这张回溯图：

　　实际上回溯时具体的方向与我们对于坐标的选取是有关系的，所以大家在写代码之前，应该先把坐标方向规定好。之后的工作就是利用flagMatrix来逐步回溯，详细的实现细节见代码。
　　5，如果还有其它更好的想法，欢迎大家与我交流^-^
　　具体代码(Java实现)：



import java.util.Scanner;

public class LCSequence {
     public static void main(String[] args) {
         String[] paras = getInput();
         System.out.println(getLongestSubsequence(paras[0], paras[1]));
     }
     
     public static String[] getInput() {
         Scanner reader = new Scanner(System.in);
         String[] paras = new String[2];
         paras[0] = reader.nextLine();
         paras[1] = reader.nextLine();
         reader.close();
         return paras;
     }
     
     public static String[][] getGenerationMatirx(String str1, String str2) {
         int[][] temp = new int[str1.length() + 1][str2.length() + 1];
         String[][] flag = new String[str1.length() + 1][str2.length() + 1];
         for (int i = 0; i <= str1.length(); i ++) {
             temp[0] = 0;
         }
         for (int i = 0; i <= str2.length(); i ++) {
             temp[0] = 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[j] = temp[i - 1][j - 1] + 1;
                     flag[j] = "left_up";
                 } else {
                     if (temp[i - 1][j] >= temp[j - 1]) {
                         temp[j] = temp[i - 1][j];
                         flag[j] = "up";
                     } else {
                         temp[j] = temp[j - 1];
                         flag[j] = "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[j].equals("left_up")) {
                     tempString += str1.charAt(i - 1);
                     i --;
                     j --;
                 } else if (flagMatrix[j].equals("left")) {
                     j --;
                 } else {
                     i --;
                 }
         }
         return new StringBuffer(tempString).reverse().toString();
     }

}
　　运行结果：

　　这里需要注意一点，因为LCS可能不止一个，所以对于flagMatrix的赋值其实不止一种情况，代码34行中大于或者大于等于都可以，但是可能会输出不同的结果。