Dynamic Programming: Grids & Strings

def longest_common_subsequence(text1: str, text2: str) -> int:
    """Length of the longest subsequence that appears in both strings."""
    m, n = len(text1), len(text2)
    # dp[i][j] = LCS length of the first i chars of text1 and the first j of text2.
    # Row 0 and column 0 stand for an empty prefix, so they stay 0.
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # Same last char: it ends the LCS of both shorter prefixes.
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # Drop the last char of one string or the other.
    return dp[m][n]


if __name__ == "__main__":
    print(longest_common_subsequence("abcde", "ace"))  # 3
    print(longest_common_subsequence("abc", "abc"))  # 3
    print(longest_common_subsequence("abc", "def"))  # 0

// Length of the longest subsequence that appears in both strings.
export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  // dp[i][j] = LCS length of the first i chars of text1 and the first j of text2.
  // Row 0 and column 0 stand for an empty prefix, so they stay 0.
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // Same last char: it ends the LCS of both shorter prefixes.
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Drop the last char of one string or the other.
      }
    }
  }
  return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace")); // 3
console.log(longestCommonSubsequence("abc", "abc")); // 3
console.log(longestCommonSubsequence("abc", "def")); // 0

package main

import "fmt"

// longestCommonSubsequence returns the length of the longest subsequence that
// appears in both strings.
func longestCommonSubsequence(text1, text2 string) int {
	m, n := len(text1), len(text2)
	// dp[i][j] = LCS length of the first i chars of text1 and the first j of text2.
	// Row 0 and column 0 stand for an empty prefix, so they stay 0.
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1 // Same last char: it ends the LCS of both shorter prefixes.
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // Drop the last char of one string or the other.
			}
		}
	}
	return dp[m][n]
}

func main() {
	fmt.Println(longestCommonSubsequence("abcde", "ace")) // 3
	fmt.Println(longestCommonSubsequence("abc", "abc"))   // 3
	fmt.Println(longestCommonSubsequence("abc", "def"))   // 0
}

using System;

public class Solution
{
    // Length of the longest subsequence that appears in both strings.
    public static int LongestCommonSubsequence(string text1, string text2)
    {
        int m = text1.Length, n = text2.Length;
        // dp[i, j] = LCS length of the first i chars of text1 and the first j of text2.
        // Row 0 and column 0 stand for an empty prefix, so they stay 0.
        var dp = new int[m + 1, n + 1];
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (text1[i - 1] == text2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1] + 1; // Same last char: it ends the LCS of both shorter prefixes.
                }
                else
                {
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]); // Drop the last char of one string or the other.
                }
            }
        }
        return dp[m, n];
    }

    public static void Main()
    {
        Console.WriteLine(LongestCommonSubsequence("abcde", "ace")); // 3
        Console.WriteLine(LongestCommonSubsequence("abc", "abc")); // 3
        Console.WriteLine(LongestCommonSubsequence("abc", "def")); // 0
    }
}

public class Solution {
    // Length of the longest subsequence that appears in both strings.
    static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // dp[i][j] = LCS length of the first i chars of text1 and the first j of text2.
        // Row 0 and column 0 stand for an empty prefix, so they stay 0.
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // Same last char: it ends the LCS of both shorter prefixes.
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Drop the last char of one string or the other.
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace")); // 3
        System.out.println(longestCommonSubsequence("abc", "abc")); // 3
        System.out.println(longestCommonSubsequence("abc", "def")); // 0
    }
}

def edit_distance(word1: str, word2: str) -> int:
    """Fewest single-character inserts, deletes or replacements that turn word1
    into word2."""
    m, n = len(word1), len(word2)
    # dp[i][j] = edits to turn the first i chars of word1 into the first j of word2.
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # Delete all i chars.
    for j in range(n + 1):
        dp[0][j] = j  # Insert all j chars.
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # Last chars already match: no edit needed.
            else:
                replace = dp[i - 1][j - 1]  # Turn word1's last char into word2's.
                remove = dp[i - 1][j]  # Delete word1's last char.
                insert = dp[i][j - 1]  # Append word2's last char.
                dp[i][j] = 1 + min(replace, remove, insert)
    return dp[m][n]


if __name__ == "__main__":
    print(edit_distance("horse", "ros"))  # 3
    print(edit_distance("intention", "execution"))  # 5
    print(edit_distance("", "abc"))  # 3

// Fewest single-character inserts, deletes or replacements that turn word1
// into word2.
export function editDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  // dp[i][j] = edits to turn the first i chars of word1 into the first j of word2.
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i; // Delete all i chars.
  for (let j = 0; j <= n; j++) dp[0][j] = j; // Insert all j chars.
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // Last chars already match: no edit needed.
      } else {
        const replace = dp[i - 1][j - 1]; // Turn word1's last char into word2's.
        const remove = dp[i - 1][j]; // Delete word1's last char.
        const insert = dp[i][j - 1]; // Append word2's last char.
        dp[i][j] = 1 + Math.min(replace, remove, insert);
      }
    }
  }
  return dp[m][n];
}

console.log(editDistance("horse", "ros")); // 3
console.log(editDistance("intention", "execution")); // 5
console.log(editDistance("", "abc")); // 3

package main

import "fmt"

// editDistance returns the fewest single-character inserts, deletes or
// replacements that turn word1 into word2.
func editDistance(word1, word2 string) int {
	m, n := len(word1), len(word2)
	// dp[i][j] = edits to turn the first i chars of word1 into the first j of word2.
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i <= m; i++ {
		dp[i][0] = i // Delete all i chars.
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j // Insert all j chars.
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1] // Last chars already match: no edit needed.
			} else {
				replace := dp[i-1][j-1] // Turn word1's last char into word2's.
				remove := dp[i-1][j]    // Delete word1's last char.
				insert := dp[i][j-1]    // Append word2's last char.
				dp[i][j] = 1 + min(replace, remove, insert)
			}
		}
	}
	return dp[m][n]
}

func main() {
	fmt.Println(editDistance("horse", "ros"))           // 3
	fmt.Println(editDistance("intention", "execution")) // 5
	fmt.Println(editDistance("", "abc"))                // 3
}

using System;

public class Solution
{
    // Fewest single-character inserts, deletes or replacements that turn word1
    // into word2.
    public static int EditDistance(string word1, string word2)
    {
        int m = word1.Length, n = word2.Length;
        // dp[i, j] = edits to turn the first i chars of word1 into the first j of word2.
        var dp = new int[m + 1, n + 1];
        for (int i = 0; i <= m; i++) dp[i, 0] = i; // Delete all i chars.
        for (int j = 0; j <= n; j++) dp[0, j] = j; // Insert all j chars.
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (word1[i - 1] == word2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1]; // Last chars already match: no edit needed.
                }
                else
                {
                    int replace = dp[i - 1, j - 1]; // Turn word1's last char into word2's.
                    int remove = dp[i - 1, j]; // Delete word1's last char.
                    int insert = dp[i, j - 1]; // Append word2's last char.
                    dp[i, j] = 1 + Math.Min(replace, Math.Min(remove, insert));
                }
            }
        }
        return dp[m, n];
    }

    public static void Main()
    {
        Console.WriteLine(EditDistance("horse", "ros")); // 3
        Console.WriteLine(EditDistance("intention", "execution")); // 5
        Console.WriteLine(EditDistance("", "abc")); // 3
    }
}

public class Solution {
    // Fewest single-character inserts, deletes or replacements that turn word1
    // into word2.
    static int editDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        // dp[i][j] = edits to turn the first i chars of word1 into the first j of word2.
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i; // Delete all i chars.
        for (int j = 0; j <= n; j++) dp[0][j] = j; // Insert all j chars.
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // Last chars already match: no edit needed.
                } else {
                    int replace = dp[i - 1][j - 1]; // Turn word1's last char into word2's.
                    int remove = dp[i - 1][j]; // Delete word1's last char.
                    int insert = dp[i][j - 1]; // Append word2's last char.
                    dp[i][j] = 1 + Math.min(replace, Math.min(remove, insert));
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(editDistance("horse", "ros")); // 3
        System.out.println(editDistance("intention", "execution")); // 5
        System.out.println(editDistance("", "abc")); // 3
    }
}