1143. Longest common subsequence

1143_solution1_tab.c

#include <stdlib.h>
#include <string.h>

static int max(int a, int b) { return a > b ? a : b; }

int longestCommonSubsequence(char *text1, char *text2) {
  int n = strlen(text1), m = strlen(text2);
  int w = m + 1;
  int *dp = calloc((n + 1) * w, sizeof(int)); // dp[i * w + j]

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (text1[i - 1] == text2[j - 1])
        dp[i * w + j] = 1 + dp[(i - 1) * w + (j - 1)];
      else
        dp[i * w + j] = max(dp[(i - 1) * w + j], dp[i * w + (j - 1)]);
    }
  }
  int res = dp[n * w + m];
  free(dp);
  return res;
}

1143_solution2_memo.c

#include <stdlib.h>
#include <string.h>

static int max(int a, int b) { return a > b ? a : b; }

static int solve(int i, int j, const char *a, const char *b, int w, int *dp) {
  if (i == 0 || j == 0)
    return 0; // one string is empty
  if (dp[i * w + j] != -1)
    return dp[i * w + j];

  if (a[i - 1] == b[j - 1])
    return dp[i * w + j] = 1 + solve(i - 1, j - 1, a, b, w, dp);
  return dp[i * w + j] =
             max(solve(i - 1, j, a, b, w, dp), solve(i, j - 1, a, b, w, dp));
}

int longestCommonSubsequence(char *text1, char *text2) {
  int n = strlen(text1), m = strlen(text2);
  int w = m + 1;
  int *dp = malloc((n + 1) * w * sizeof(int)); // dp[i * w + j]
  for (int k = 0; k < (n + 1) * w; k++)
    dp[k] = -1;
  int res = solve(n, m, text1, text2, w, dp);
  free(dp);
  return res;
}

1143_solution1_tab.cpp

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size(), m = text2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (text1[i - 1] == text2[j - 1])
          dp[i][j] = 1 + dp[i - 1][j - 1];
        else
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
    return dp[n][m];
  }
};

1143_solution2_memo.cpp

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  int solve(int i, int j, string &a, string &b, vector<vector<int>> &dp) {
    if (i == 0 || j == 0)
      return 0; // one string is empty
    if (dp[i][j] != -1)
      return dp[i][j];

    if (a[i - 1] == b[j - 1])
      return dp[i][j] = 1 + solve(i - 1, j - 1, a, b, dp);
    return dp[i][j] = max(solve(i - 1, j, a, b, dp), solve(i, j - 1, a, b, dp));
  }

  int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size(), m = text2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
    return solve(n, m, text1, text2, dp);
  }
};

1143_solution1_tab.go

package dp

func longestCommonSubsequence(text1 string, text2 string) int {
    n, m := len(text1), len(text2)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = 1 + dp[i-1][j-1]
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[n][m]
}

1143_solution2_memo.go

package dp

func longestCommonSubsequence(text1 string, text2 string) int {
    n, m := len(text1), len(text2)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var solve func(i, j int) int
    solve = func(i, j int) int {
        if i == 0 || j == 0 {
            return 0 // one string is empty
        }
        if dp[i][j] != -1 {
            return dp[i][j]
        }

        if text1[i-1] == text2[j-1] {
            dp[i][j] = 1 + solve(i-1, j-1)
        } else {
            dp[i][j] = max(solve(i-1, j), solve(i, j-1))
        }
        return dp[i][j]
    }

    return solve(n, m)
}

1143_solution1_tab.java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(), m = text2.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
}

1143_solution2_memo.java

import java.util.Arrays;

class Solution {
    private int solve(int i, int j, String a, String b, int[][] dp) {
        if (i == 0 || j == 0)
            return 0; // one string is empty
        if (dp[i][j] != -1)
            return dp[i][j];

        if (a.charAt(i - 1) == b.charAt(j - 1))
            return dp[i][j] = 1 + solve(i - 1, j - 1, a, b, dp);
        return dp[i][j] = Math.max(solve(i - 1, j, a, b, dp), solve(i, j - 1, a, b, dp));
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(), m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int[] row : dp)
            Arrays.fill(row, -1);
        return solve(n, m, text1, text2, dp);
    }
}

1143_solution1_tab.js

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const n = text1.length, m = text2.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (text1[i - 1] === text2[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[n][m];
};

1143_solution2_memo.js

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const n = text1.length, m = text2.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(-1));

  const solve = (i, j) => {
    if (i === 0 || j === 0) return 0; // one string is empty
    if (dp[i][j] !== -1) return dp[i][j];

    if (text1[i - 1] === text2[j - 1]) return (dp[i][j] = 1 + solve(i - 1, j - 1));
    return (dp[i][j] = Math.max(solve(i - 1, j), solve(i, j - 1)));
  };

  return solve(n, m);
};

1143_solution1_tab.py

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

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[n][m]

1143_solution2_memo.py

import sys


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        sys.setrecursionlimit(max(1000, 2 * (n + m) + 100))  # depth can reach n + m
        dp = [[-1] * (m + 1) for _ in range(n + 1)]

        def solve(i: int, j: int) -> int:
            if i == 0 or j == 0:
                return 0  # one string is empty
            if dp[i][j] != -1:
                return dp[i][j]

            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = 1 + solve(i - 1, j - 1)
            else:
                dp[i][j] = max(solve(i - 1, j), solve(i, j - 1))
            return dp[i][j]

        return solve(n, m)

1143_solution1_tab.rs

impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        let (a, b) = (text1.as_bytes(), text2.as_bytes());
        let (n, m) = (a.len(), b.len());
        let mut dp = vec![vec![0; m + 1]; n + 1];

        for i in 1..=n {
            for j in 1..=m {
                dp[i][j] = if a[i - 1] == b[j - 1] {
                    1 + dp[i - 1][j - 1]
                } else {
                    dp[i - 1][j].max(dp[i][j - 1])
                };
            }
        }
        dp[n][m]
    }
}

1143_solution2_memo.rs

impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        let (a, b) = (text1.as_bytes(), text2.as_bytes());
        let (n, m) = (a.len(), b.len());
        let mut dp = vec![vec![-1; m + 1]; n + 1];
        Self::solve(n, m, a, b, &mut dp)
    }

    fn solve(i: usize, j: usize, a: &[u8], b: &[u8], dp: &mut Vec<Vec<i32>>) -> i32 {
        if i == 0 || j == 0 {
            return 0; // one string is empty
        }
        if dp[i][j] != -1 {
            return dp[i][j];
        }

        dp[i][j] = if a[i - 1] == b[j - 1] {
            1 + Self::solve(i - 1, j - 1, a, b, dp)
        } else {
            Self::solve(i - 1, j, a, b, dp).max(Self::solve(i, j - 1, a, b, dp))
        };
        dp[i][j]
    }
}