首页 > 代码库 > 72. Edit Distance && 161. One Edit Distance
72. Edit Distance && 161. One Edit Distance
72. Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Classic DP problem. DP feels like mathematical induction
/** * dp[r][c] indicates the minimum number of operations to convert word1[0,r] to word2[0,c] * boundary conditions: * dp[r][0] = r * dp[0][c] = c * <p> * if word1[r] == word2[c]: dp[r][c] = dp[r-1][c-1] * else: dp[r][c] = min(dp[r-1][c-1]+1, dp[r-1][c]+1, dp[r][c-1]+1) * <p> * dp[r-1][c-1]+1 means "replace the last character of word1 with the last character of word2" * dp[r-1][c]+1 means "delete the last character from word1": * dp[r-1][c] already matches. The extra word1[r] is useless, so we remove it * dp[r][c-1]+1 means "add the last character of word2 to the end of word1": * dp[r][c-1] already matches. In order to match word2[c], we need to add it to the end of word1 */class Solution { public int minDistance(String word1, String word2) { int ROW = word1.length(); int COL = word2.length(); int[][] dp = new int[ROW + 1][COL + 1]; for (int r = 1; r <= ROW; ++r) dp[r][0] = r; for (int c = 1; c <= COL; ++c) dp[0][c] = c; for (int r = 1; r <= ROW; ++r) { for (int c = 1; c <= COL; ++c) { if (word1.charAt(r - 1) == word2.charAt(c - 1)) dp[r][c] = dp[r - 1][c - 1]; else dp[r][c] = Math.min(dp[r - 1][c - 1] + 1, Math.min(dp[r][c - 1] + 1, dp[r - 1][c] + 1)); } } return dp[ROW][COL]; }}
161. One Edit Distance
Given two strings S and T, determine if they are both one edit distance apart.
72. Edit Distance && 161. One Edit Distance
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。