题解 | 最长公共子序列(二)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
       String[][] dp=new String[s1.length()+1][s2.length()+1];
       s1=" "+s1;
       s2=" "+s2;
       for(int k=0;k<s1.length();k++){
          for(int t=0;t<s2.length();t++){
            dp[k][t]="";
          }
       }
       String max ="";
       for(int i=1;i<s1.length();i++){
          for(int j=1;j<s2.length();j++){
            if(s1.charAt(i)==s2.charAt(j)){
               dp[i][j]=dp[i-1][j-1]+s1.charAt(i);
            }else{
             dp[i][j]=dp[i-1][j].length()>dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
            }
           max = dp[i][j].length()>max.length()?dp[i][j]:max;
          }
       }
       if(max.equals("")){

        return "-1";
       }
              return max;
     }
          
       }
    

由于i-1和j-1会出错，就在两个字符串的前面加个空字符串，再给dp数组每个元素都设置成空字符串，然后可按照逻辑处理；当然这时候逻辑处理应该从i=1和j=1开始