1143. Longest Common Subsequence

LeetCode medium original: C# #array #csharp #dynamic-programming #leetcode #math #medium #recursion #string #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

given две строки text1 и text2. return длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, return 0.

subsequence строки — это новая string, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.

НаExample, "ace" является subsequenceю "abcde".

Общая subsequence двух строк — это subsequence, которая является общей для обеих строк.

Example:

Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.

C# solution

matched/original

public class Solution {
    private int[][] memo;
    private string text1;
    private string text2;
    
    public int LongestCommonSubsequence(string text1, string text2) {
        this.text1 = text1;
        this.text2 = text2;
        memo = new int[text1.Length + 1][];
        for (int i = 0; i < text1.Length + 1; i++) {
            memo[i] = new int[text2.Length + 1];
            Array.Fill(memo[i], -1);
        }
        return MemoSolve(0, 0);
    }
    
    private int MemoSolve(int p1, int p2) {
        if (p1 == text1.Length || p2 == text2.Length) return 0;
        if (memo[p1][p2] != -1) return memo[p1][p2];
        int answer;
        if (text1[p1] == text2[p2]) {
            answer = 1 + MemoSolve(p1 + 1, p2 + 1);
        } else {
            answer = Math.Max(MemoSolve(p1, p2 + 1), MemoSolve(p1 + 1, p2));
        }
        memo[p1][p2] = answer;
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int[][] memo;
    private string text1;
    private string text2;
    
    public int LongestCommonSubsequence(string text1, string text2) {
        this.text1 = text1;
        this.text2 = text2;
        memo = new int[text1.size() + 1][];
        for (int i = 0; i < text1.size() + 1; i++) {
            memo[i] = new int[text2.size() + 1];
            Array.Fill(memo[i], -1);
        }
        return MemoSolve(0, 0);
    }
    
    private int MemoSolve(int p1, int p2) {
        if (p1 == text1.size() || p2 == text2.size()) return 0;
        if (memo[p1][p2] != -1) return memo[p1][p2];
        int answer;
        if (text1[p1] == text2[p2]) {
            answer = 1 + MemoSolve(p1 + 1, p2 + 1);
        } else {
            answer = max(MemoSolve(p1, p2 + 1), MemoSolve(p1 + 1, p2));
        }
        memo[p1][p2] = answer;
        return answer;
    }
}

Java solution

matched/original

class Solution {
    
  private int[][] memo;
  private String text1;
  private String text2;
    
  public int longestCommonSubsequence(String text1, String text2) {
    this.memo = new int[text1.length() + 1][text2.length() + 1];
    for (int i = 0; i < text1.length(); i++) {
      for (int j = 0; j < text2.length(); j++) {
        this.memo[i][j] = -1;
      }
    }
    this.text1 = text1;
    this.text2 = text2;
    return memoSolve(0, 0);
  }

  private int memoSolve(int p1, int p2) {        
    if (memo[p1][p2] != -1) {
      return memo[p1][p2];
    }

    int answer = 0;
    if (text1.charAt(p1) == text2.charAt(p2)) {
      answer = 1 + memoSolve(p1 + 1, p2 + 1);
    } else {
      answer = Math.max(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2));
    }
    
    memo[p1][p2] = answer;
    return memo[p1][p2];
  }
}

JavaScript solution

matched/original

var longestCommonSubsequence = function(text1, text2) {
    const memo = Array.from({ length: text1.length + 1 }, () => Array(text2.length + 1).fill(-1));
    
    const memoSolve = (p1, p2) => {
        if (p1 === text1.length || p2 === text2.length) return 0;
        if (memo[p1][p2] !== -1) return memo[p1][p2];
        let answer;
        if (text1[p1] === text2[p2]) {
            answer = 1 + memoSolve(p1 + 1, p2 + 1);
        } else {
            answer = Math.max(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2));
        }
        memo[p1][p2] = answer;
        return answer;
    };
    
    return memoSolve(0, 0);
};

Algorithm

1⃣Создайте двумерный array memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте array значением -1, чтобы указать, что эти ячейки еще не были рассчитаны.

2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и returns длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, find максимум между рекурсивными вызовами с измененными указателями.

3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.