Leetcode 1143) Longest Common Subsequence

12 Aug 2021 in Algorithms

Back To Back SWE’s Solution

https://yejip.com/algo/2021-05-13-LeetcodeStr139/

내 답안

class Solution {
    int[][] memoization;
    public int longestCommonSubsequence(String text1, String text2) {
        memoization = new int[text1.length()+1][text2.length()+1];
        for (int[] row : memoization){
            Arrays.fill(row, -1);
         }
        
        return lcs(text1,text2);
    }
    
    public int lcs(String a, String b){
        if(a.length()==0 || b.length()==0){
            return 0;
        }
        int aLen = a.length();
        int bLen = b.length();
        
         if(memoization[aLen][bLen]!=-1){
             return memoization[aLen][bLen];
        }
        
        int res= 0;
        if(a.substring(aLen-1).equals(b.substring(bLen-1))){
            res = 1+lcs(a.substring(0,aLen-1),b.substring(0,bLen-1));
        }else{
            res= Math.max(lcs(a.substring(0,aLen-1),b),lcs(a,b.substring(0,bLen-1)));
        }
        //len이 유니크할 수 밖에 없다. 첫번쨰 원소 꼭 포함하는 거니까..
        memoization[aLen][bLen]=res;
        return res;
    }
}

다른 답안

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if(text1.length() == 0 || text2.length() == 0)
            return 0;
        char[] text1Arr = text1.toCharArray();
        char[] text2Arr = text2.toCharArray();
        int row = text1.length()+1;
        int column = text2.length()+1;
        int[][] dp = new int[row][column];
        
        for(int i = 1; i< row; i++){
            for(int j =1; j< column; j++){
                if(text1Arr[i-1] == text2Arr[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]);
                }
            }
        }
        return dp[row-1][column-1];
      /*  textArr1 = text1.toCharArray();
        textArr2 = text2.toCharArray();
        int count = lcs(0, 0);
       return count;*/
    }
    
   /* public int lcs1(String text1, String text2){
        if(text1.length() == 0 || text2.length() == 0)
            return 0;
        if(text1.substring(0) == text2.substring(0)){
            return 1 + lcs1(text1.substring(1, text1.length()), text2.substring(1, text2.length()));
        } else {
            return Math.max(lcs1(text1.substring(1, text1.length()), text2), lcs1(text1, text2.substring(1, text2.length())));
        }
    }
    
    public char[] textArr1;
      public char[] textArr2;
    
    public int lcs(int i, int j){
        if(i == textArr1.length || j == textArr2.length)
            return 0;
        if(textArr1[i] == textArr2[j]){
            return 1 + lcs(i+1, j+1);
        } else {
            return Math.max(lcs(i,j+1), lcs(i+1, j));
        }
    }*/
}

오답

• Memoization 을 안했다.