Java动态规划算法解决LCS问题

Myth丶恋晨 2024-02-19 16:53 47阅读 0赞

最近项目中遇到LCS问题，于是研究了下，写了一个简单的实现

public class LongestCommonSubsequence {
    
        /**
         * 获得所有子结构的LCS长度，并存储LCS路线供getLCS方法使用，用来判断LCS的下一个子结果集
         * @param text1 :
         * @param text2 :
         * @return : map
         */
        @SuppressWarnings({ "unchecked", "rawtypes" })
        private static Map lcsLength(String[] text1,String[] text2){
            int m = text1.length;
            int n = text2.length;
            int[][] lengths = new int[m][n];
            String[][] lenFlags = new String[m][n];
            for(int i=0;i<lengths.length;i++){
                int[] vals=lengths[i];
                for(int j=0;j<vals.length;j++){
                    lengths[i][j]=0;
                    if(text1[i].equals(text2[j])){
                        if(i==0 || j==0){
                            lengths[i][j]=1;
                            lenFlags[i][j]="LeftUp";
                        }else{
                            lengths[i][j]=lengths[i-1][j-1]+1;
                            lenFlags[i][j]="LeftUp";
                        }
                        System.out.print(lengths[i][j]+" "+lenFlags[i][j]+" ");
                    }else{
                        if(i==0 || j==0){
                            lengths[i][j]=0;
                        }else{
                            if(lengths[i][j-1]>=lengths[i-1][j]){
                                lengths[i][j]=lengths[i][j-1];
                                lenFlags[i][j]="Left";
                            }else{
                                lengths[i][j]=lengths[i-1][j];
                                lenFlags[i][j]="Up";
                            }
                        }
                        System.out.print(lengths[i][j]+" "+lenFlags[i][j]+" ");
                    }
                }
                System.out.println();
            }
            Map map=new HashMap<String,String[][]>();
            map.put("lengths", lengths);
            map.put("lenFlags", lenFlags);
            return map;
        }
        /**
         * 由最后一个字符开始，判断最后一个字符是否属于LCS，属于则打印，不属于，则通过lenFlags判断下一个LCS在哪个结果集中
         * @param lenFlags 判断最佳优子结构在哪个结果集
         * @param text1 :
         * @param text2 :
         * @param text1LastIndex :
         * @param text2LastIndex :
         */
        private static void getLCS(String[][] lenFlags,String[] text1,String[] text2,int text1LastIndex,int text2LastIndex){
            if(text1LastIndex==-1 || text2LastIndex==-1){
                System.out.println("");
                System.exit(0);
            }
            String lenFlag = lenFlags[text1LastIndex][text2LastIndex];
            String[] rText1 = new String[text1LastIndex];
            String[] rText2 = new String[text2LastIndex];
            System.arraycopy(text1, 0, rText1, 0, text1LastIndex);
            System.arraycopy(text2, 0, rText2, 0, text2LastIndex);
            if("LeftUp".equals(lenFlag)){
                System.out.print(""+text1[text1LastIndex]);
                getLCS(lenFlags,rText1,rText2,text1LastIndex-1,text2LastIndex-1);
            }else{
                if("Up".equals(lenFlag)){
                    getLCS(lenFlags,rText1,text2,text1LastIndex-1,text2LastIndex);
                }else{
                    getLCS(lenFlags,text1,rText2,text1LastIndex,text2LastIndex-1);
                }
            }
        }
        @SuppressWarnings("rawtypes")
        public static void main(String[] args) {
            String[] text1="ABCDEFGHJK".split("");
            String[] text2="ABCEFGNNJJ".split("");
            Map map=lcsLength(text1,text2);
            String[][] lenFlags=(String[][])map.get("lenFlags");
            getLCS(lenFlags,text1,text2,text1.length-1,text2.length-1);
        }
    
    }