Unique Paths (LeetCode 62)

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

Type	Value
Time	O(m*n)
Space	O(m*n)

• Approach: Use a 2D array dp where dp[i][j] represents the number of unique paths to reach cell (i, j). The number of paths to (i, j) is the sum of paths from (i-1, j) (above) and (i, j-1) (left).
• Dry run (m=3, n=2):
  • initialize paths in row 0 and col 0 to 1
  • dp = [[1, 1],
    [1, ?],
    [1, ?]]
  • i=1, j=1: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
  • i=2, j=1: dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
  • result: dp[2][1] = 3

---

Edit Distance (LeetCode 72)

72. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        int dp[][]=new int[m+1][n+1];
        for(int i=1;i<=m;i++) dp[i][0]=i;
        for(int i=1;i<=n;i++) dp[0][i]=i;
        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];
                }else{
                    int tl=dp[i-1][j-1];
                    int t=dp[i-1][j];
                    int l=dp[i][j-1];
                    dp[i][j]=Math.min(l,Math.min(tl,t))+1;
                }
            }
        }
            return dp[m][n];
    }
}

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

        for i in range(1, m + 1):
            dp[i][0] = i
        for j in range(1, n + 1):
            dp[0][j] = j

        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]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

        return dp[m][n]

Type	Value
Time	O(m*n)
Space	O(m*n)

• Approach: Use a 2D DP array where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2. If the characters match, dp[i][j] = dp[i-1][j-1]. Otherwise, consider insertion (dp[i][j-1]), deletion (dp[i-1][j]), and substitution (dp[i-1][j-1]) and add 1 to the minimum of these.
• Dry run (word1="sea", word2="eat"):
  • Initialize dp: sizes 4x4. dp[i][0] = i, dp[0][j] = j.
  • i=1 ('s'), j=1 ('e'): no match -> min(dp[0][0], dp[1][0], dp[0][1]) + 1 = min(0, 1, 1) + 1 = 1
  • i=1 ('s'), j=2 ('a'): no match -> min(dp[0][1], dp[1][1], dp[0][2]) + 1 = min(1, 1, 2) + 1 = 2
  • i=2 ('e'), j=1 ('e'): match -> dp[1][0] = 1.
  • i=3 ('a'), j=2 ('a'): match -> inherits dp[2][1], which eventually leads to optimal min distance 2.