<commit_before>package algorithms.dp;

public class LongestCommonSubsequence {

  public int lcs(String s1, String s2) {
    return lcs(s1, s2, s1.length(), s2.length());
  }

  private int lcs(String s1, String s2, int i, int j) {
    if (i == 0 || j == 0) {
      return 0;
    } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
      return lcs(s1, s2, i - 1, j - 1) + 1;
    } else {
      return Math.max(lcs(s1, s2, i, j - 1), lcs(s1, s2, i - 1, j));
    }
  }

  public int lcsTabulated(String s1, String s2) {
    int[][] table = new int[s1.length() + 1][s2.length() + 1];

    for (int i = 1; i < table.length; i++) {
      for (int j = 1; j < table[0].length; j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
          table[i][j] = table[i - 1][j - 1] + 1;
        } else {
          table[i][j] = Math.max(table[i][j - 1], table[i - 1][j]);
        }
      }
    }

    return table[s1.length()][s2.length()];
  }

  public static void main(String[] args) {
    LongestCommonSubsequence lcs = new LongestCommonSubsequence();
    System.out.println(lcs.lcsTabulated("Aerodrone", "Airpod"));
    System.out.println(lcs.lcsTabulated("AGGRTAB", "GXTXAYB"));
  }
}<commit_msg>Add memoized solution as well<commit_after>package algorithms.dp;

public class LongestCommonSubsequence {

  public int lcs(String s1, String s2) {
    return lcs(s1, s2, s1.length(), s2.length());
  }

  private int lcs(String s1, String s2, int i, int j) {
    if (i == 0 || j == 0) {
      return 0;
    } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
      return lcs(s1, s2, i - 1, j - 1) + 1;
    } else {
      return Math.max(lcs(s1, s2, i, j - 1), lcs(s1, s2, i - 1, j));
    }
  }

  public int lcsTabulated(String s1, String s2) {
    int[][] table = new int[s1.length() + 1][s2.length() + 1];

    for (int i = 1; i < table.length; i++) {
      for (int j = 1; j < table[0].length; j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
          table[i][j] = table[i - 1][j - 1] + 1;
        } else {
          table[i][j] = Math.max(table[i][j - 1], table[i - 1][j]);
        }
      }
    }

    return table[s1.length()][s2.length()];
  }

  public int lcsMemoized(String s1, String s2) {
    return lcsMemoized(s1, s2, s1.length(), s2.length(), new int[s1.length()][s2.length()]);
  }

  private int lcsMemoized(String s1, String s2, int i, int j, int[][] results) {
    if (i == 0 || j == 0) {
      return 0;
    }

    if (results[i - 1][j - 1] == 0) {
      if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
        results[i - 1][j - 1] = lcsMemoized(s1, s2, i - 1, j - 1, results) + 1;
      } else {
        results[i - 1][j - 1] = Math.max(lcsMemoized(s1, s2, i, j - 1, results),
            lcsMemoized(s1, s2, i - 1, j, results));
      }
    }
    return results[i - 1][j - 1];
  }

  public static void main(String[] args) {
    LongestCommonSubsequence lcs = new LongestCommonSubsequence();
    System.out.println(lcs.lcsTabulated("AerodroneAerodroneAerodrone", "AirpodAiAirpodrpod"));
    //System.out.println(lcs.lcsTabulated("AGGRTAB", "GXTXAYB"));
    System.out.println(lcs.lcsMemoized("AerodroneAerodroneAerodrone", "AirpodAiAirpodrpod"));
  }
}
{'fraction_non_alphanumeric': 0.18822788794460182, 'fraction_numerical': 0.04060434372049103, 'mean_word_length': 2.4431202600216686, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2978754', 'n_tokens_mistral': 1391, 'n_tokens_neox': 1306, 'n_words': 311}