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

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 maxLengthString = "";
        ArrayList<Node> myNode = new ArrayList<Node>();
        for(int i = s1.length() - 1; i>= 0; i--){
            char temC = s1.charAt(i);
            ArrayList<Node> temList = new ArrayList<Node>();
            for(int j =s2.length() - 1; j>= 0; j--){
                char temC1 = s2.charAt(j);
                if(temC1 == temC){
                    String temString = "";
                    Node temNode1 = new Node();
                    for(int jj = 0; jj<myNode.size(); jj++){
                        Node temNode = myNode.get(jj);
                        if(temNode.index > j && temNode.s.length() > temString.length()){
                            temString  = temNode.s;
                        }
                    }
                    temNode1.s = temC + temString;
                    if(temNode1.s.length() > maxLengthString.length()){
                    maxLengthString = temNode1.s;
                    }
                    temNode1.index = j;
                    temList.add(temNode1);
                }
            }
            for(int j = 0; j<temList.size();j++){
                myNode.add(temList.get(j));
            }
        }
        for(int i = 0; i<myNode.size(); i++){
           // System.out.println(myNode.get(i).s);
        }
        if(maxLengthString.length() == 0){
            return "-1";
        }
        return maxLengthString;
        /*
        subString(s1,s2,0,0,"");
        String maxString = "";
        if(maxLength == 0){
            return "-1";
        }
        for(int i = 0;i<myList.size(); i++){
             //System.out.println(myList.get(i));
            if(maxString.length() < myList.get(i).length()){
               
                maxString = myList.get(i);
            }
        }
        return maxString;
        
        */
    }
    class Node{
        String s;
        int index;
    }
    
    /*
    ArrayList<String> myList = new ArrayList<String>();
    int maxLength = 0;
    private void subString(String s1,String s2,int index1,int index2,String nowString){
        //System.out.println(nowString + ": "+ index1 + " "+index2);
        if(index1 >= s1.length() || index2 >= s2.length() ){
            if(nowString.length() != 0){
             if(nowString.length() > maxLength){
                   maxLength= nowString.length();
                    myList.add(nowString);
                }
            }
            return ;
        }
        char temC = s1.charAt(index1);
        int index22 = -1;
        for(int i = index2; i< s2.length(); i++){
            char temC2 = s2.charAt(i);
            if(temC == temC2){
                 index22 = i+1;
                break;
            }
        }
        if(index22 != -1){
            subString(s1,s2,index1+1,index22,nowString + temC);
        }
        subString(s1,s2,index1+1,index2,nowString);
        
    }
    */
}