题解 | #最长公共子序列#
最长公共子序列
http://www.nowcoder.com/questionTerminal/6d29638c85bb4ffd80c020fe244baf11
public String LCS (String s1, String s2) { // 设置状态变量dp[i][j]:表示下标为[0,i-1]的s1和下标为[0,j-1]的s2的最长公共子序列的大小 int[][] dp=new int[s1.length()+1][s2.length()+1]; for (int i=1;i<s1.length()+1;i++){ for (int j=1;j<s2.length()+1;j++){ if (s1.charAt(i-1)==s2.charAt(j-1)){ dp[i][j]=dp[i-1][j-1]+1; }else { dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); } } } int len1=s1.length(); int len2=s2.length(); StringBuilder sb = new StringBuilder(); while (len1>0&&len2>0){ //如果两个位置的字符相等,直接添加进sb中 if (s1.charAt(len1-1)==s2.charAt(len2-1)){ sb.append(s1.charAt(len1-1)); len1--; len2--; }else {//如果不相等,则要根据dp[][]来判断应该向哪个方向移动 if (dp[len1][len2-1]>dp[len1-1][len2]){//说明len2方向的有更多相同的字符,所以len2-- // 说明dp[len1][len2]==dp[len1][len2-1], len2--; }else { len1--; } } } if (sb.length() == 0) return "-1"; return sb.reverse().toString(); }