Skip to main content

1143. Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/

Python​

Top-Down DP from right​

from functools import cache


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dp(cur1, cur2):
            if cur1 == -1 or cur2 == -1:
                return 0

            if text1[cur1] == text2[cur2]:
                return 1 + dp(cur1-1, cur2-1)

            return max(dp(cur1, cur2-1), dp(cur1-1, cur2))

        return dp(len(text1)-1, len(text2)-1)

Top-Down DP from left​

from functools import cache


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dp(cur1, cur2):
            if cur1 == len(text1) or cur2 == len(text2):
                return 0

            if text1[cur1] == text2[cur2]:
                return 1 + dp(cur1+1, cur2+1)

            return max(dp(cur1, cur2+1), dp(cur1+1, cur2))

        return dp(0, 0)

Bottom-UP DP​

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]

        for col in range(len(text2)-1, -1, -1):
            for row in range(len(text1)-1, -1, -1):
                if text2[col] == text1[row]:
                    dp[row][col] = 1 + dp[row+1][col+1]
                else:
                    dp[row][col] = max(dp[row+1][col], dp[row][col+1])
        return dp[0][0]

Javascript​

var longestCommonSubsequence = function(text1, text2) {
    const dp = [...new Array(text1.length + 1)].map(() => new Array(text2.length + 1).fill(0));

    for (let i = 0; i <= text1.length; i++) {
        for (let j = 0; j <= text2.length; j++) {

            if (i === 0 || j === 0) dp[i][j] = 0;
            else {
                if (text1[i - 1] === text2[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[text1.length][text2.length];
};

/**
 *   0 a c e
 * 0 0 0 0 0
 * a 0 1 1 1
 * b 0 1 1 1
 * c 0 1 2 2
 * d 0 1 2 2
 * e 0 1 2 3
 */

Rust​

Bottom-Up DP​

use std::cmp::max;


impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        let text1_len = text1.chars().count();
        let text2_len = text2.chars().count();

        let mut dp = vec![
            vec![0; text2_len+1];
            text1_len+1
        ];

        for row in (0..text1_len).rev() {
            for col in (0..text2_len).rev() {
                let letter1 = text1.chars().nth(row).unwrap();
                let letter2 = text2.chars().nth(col).unwrap();

                dp[row][col] = if letter1 == letter2 {
                    dp[row+1][col+1] + 1
                } else {
                    max(dp[row+1][col], dp[row][col+1])
                }
            }
        }

        dp[0][0]
    }
}