石家庄园林绿化建设招标网站,马鞍山网站开发流程,重庆本地网站论坛有哪些,辽宁省交通建设投资集团网站①、两个字符串的删除操作 给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 事例#xff1a; 输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 事例 输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变为 ea 第二步将 eat 变为 ea 思路 使用动态规划dp定义为dp[i][j]表示word1从0到i - 1要跟word2从0到j - 1相同的最小删除次数。若word1[i - 1] word2[j - 1]则此时不需要删除dp[i][j] dp[i - 1][j - 1]。若不相同则需要删除其中一个若删除word1则dp变为i - 1与j匹配dp[i][j] dp[i - 1][j] 1若删除word2则dp变为i与j - 1匹配dp[i][j] dp[i][j - 1] 1两者选择最小值即可。
动态规划 dp定义及含义dp[i][j]表示word1从0到i - 1要跟word2从0到j - 1相同的最小删除次数。 状态转移方程if(word1[i - 1] word2[j - 1]) dp[i][j] dp[i - 1][j - 1] else dp[i][j] Math.min(dp[i - 1][j] 1,dp[i][j - 1] 1) 初始化第一行和第一列表示一个字符串到空串需要删除多少次其实就是删除另一个字符串的长度dp[i][0] i , dp[0][j] j。 遍历顺序两个for循环嵌套遍历 dp[word1.length()][word2.length()]即为答案。
代码
public int minDistance(String word1, String word2) {int[][] dp new int[word1.length() 1][word2.length() 1];for(int i 1;i word1.length();i){dp[i][0] i;}for(int j 1;j word2.length();j){dp[0][j] j;}for(int i 1;i word1.length();i){for(int j 1;j word2.length();j){if(word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] Math.min(dp[i - 1][j] 1,dp[i][j - 1] 1);}}}return dp[word1.length()][word2.length()];}
②、编辑距离 给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作 插入一个字符删除一个字符替换一个字符 事例 输入word1 horse, word2 ros
输出3
解释
horse - rorse (将 h 替换为 r)
rorse - rose (删除 r)
rose - ros (删除 e) 思路 与上一题类似只是这道题多了插入和替换操作。对于两个字符串其实存在逆向操作如像word1添加一个字符也可以换为让word2删除一个字符。故不需要考虑只向word1或word2操作和不需要考虑添加删除操作只需要考虑删除和替换操作。
删除与上题一样替换操作理解成word1与word2需要替换其中一个字符则只需要操作一次在两者的前一个字符中选择一个替换即dp[i][j] dp[i - 1][j - 1] 1。
动态规划 dp定义及含义dp[i][j]表示word1从0到i - 1要跟word2从0到j - 1相同需要操作多少次。 状态转移方程if(word1[i - 1] word[j - 1]) dp[i][j] dp[i - 1][j - 1] else dp[i][j] Math.min(dp[i - 1][j] 1,dp[i][j - 1] 1,dp[i - 1][j - 1] 1)。 初始化dp[i][0] i,dp[0][j] j 遍历顺序两个for循环嵌套遍历 dp[word1.length()][word2.length()]即为答案。
代码
public int minDistance(String word1, String word2) {int[][] dp new int[word1.length() 1][word2.length() 1];for(int i 1;i word1.length();i){dp[i][0] i;}for(int j 1;j word2.length();j){dp[0][j] j;}for(int i 1;i word1.length();i){for(int j 1;j word2.length();j){if(word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] Math.min(dp[i - 1][j] 1,Math.min(dp[i][j - 1] 1,dp[i - 1][j - 1] 1));}}}return dp[word1.length()][word2.length()];}
参考代码随想录 (programmercarl.com)
