LeetCode 75
Edit Distance
- Problem
- LC 72
- Topic
- DP 1D
- File
- official75_LC72EditDistance.java
- Path
- pkg5leetcode/official75/official75_LC72EditDistance.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC72EditDistance.java
- Approach
- 2D DP min ops insert/delete/replace.
- Complexity
- Time O(mn), Space O(mn)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Edit Distance | LC 725 * APPROACH: 2D DP min ops insert/delete/replace.6 * COMPLEXITY: Time O(mn), Space O(mn)7 */8public class official75_LC72EditDistance {9 static int minDistance(String word1, String word2) {10 int m = word1.length(), n = word2.length();11 int[][] dp = new int[m + 1][n + 1];12 for (int i = 0; i <= m; i++) dp[i][0] = i;13 for (int j = 0; j <= n; j++) dp[0][j] = j;14 for (int i = 1; i <= m; i++)15 for (int j = 1; j <= n; j++)16 if (word1.charAt(i - 1) == word2.charAt(j - 1))17 dp[i][j] = dp[i - 1][j - 1];18 else19 dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));20 return dp[m][n];21 }22 23 public static void main(String[] args) {24 check(minDistance("horse", "ros") == 3, "case1");25 check(minDistance("intention", "execution") == 5, "case2");26 System.out.println("all tests passed");27 }28 29 static void check(boolean cond, String name) {30 if (!cond) throw new AssertionError("FAILED: " + name);31 System.out.println(" PASS " + name);32 }33}