题目描述:给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public int minDistance(String word1, String word2) { char[] nums1 = word1.toCharArray(); char[] nums2 = word2.toCharArray(); int longestCommon = longestCommonSubsequence(nums1, nums2); return nums1.length + nums2.length - longestCommon * 2; }
private int longestCommonSubsequence(char[] nums1, char[] nums2) { int[][] dp = new int[nums1.length + 1][nums2.length + 1]; for (int i = 1; i <= nums1.length; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[nums1.length][nums2.length]; } }
|