Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtwo-dimensional-dp

Longest Common Subsequence

Problem (restated)

Lengths of longest subsequence common to text1 and text2 (not necessarily contiguous).

Intuition

dp[i][j] = LCS of prefixes. Equal → +1 diagonal; else max(skip either).

Approaches

Classic LCS DP

Tested only

Time O(mn)Space O(min(m,n))

Idea. 1D rolling: dp[j] previous row; track prev diagonal carefully.

Walkthrough. abcde vs ace → 3.

Trade-offs. Edit distance is the same grid with different recurrences.

Solution

export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    let prev = 0;
    for (let j = 1; j <= n; j++) {
      const tmp = dp[j]!;
      if (text1[i - 1] === text2[j - 1]) dp[j] = prev + 1;
      else dp[j] = Math.max(dp[j]!, dp[j - 1]!);
      prev = tmp;
    }
  }
  return dp[n]!;
}

export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    let prev = 0;
    for (let j = 1; j <= n; j++) {
      const tmp = dp[j]!;
      if (text1[i - 1] === text2[j - 1]) dp[j] = prev + 1;
      else dp[j] = Math.max(dp[j]!, dp[j - 1]!);
      prev = tmp;
    }
  }
  return dp[n]!;
}

Template connection

Two-dimensional DP on two strings.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?