大佬教程收集整理的这篇文章主要介绍了编辑距离 - 动态规划,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
https://leetcode-cn.com/problems/edit-distance/
思路一:动态规划来做
public int minDistance(String word1, String word2) { if (word1 == null || word2 == null) return 0; char[] cs1 = word1.toCharArray(); char[] cs2 = word2.toCharArray(); int[][] dp = new int[cs1.length + 1][cs2.length + 1]; dp[0][0] = 0; // 第0列 for (int i = 1; i <= cs1.length; i++) { dp[i][0] = i; } // 第0行 for (int j = 1; j <= cs2.length; j++) { dp[0][j] = j; } // 其他行其他列 for (int i = 1; i <= cs1.length; i++) { for (int j = 1; j <= cs2.length; j++) { int top = dp[i - 1][j] + 1; int left = dp[i][j - 1] + 1; int leftTop = dp[i - 1][j - 1]; if (cs1[i - 1] != cs2[j - 1]) { leftTop++; } dp[i][j] = Math.min(Math.min(top, left), leftTop); } } return dp[cs1.length][cs2.length]; }
以上是大佬教程为你收集整理的编辑距离 - 动态规划全部内容,希望文章能够帮你解决编辑距离 - 动态规划所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。