583. Delete Operation for Two Strings (Medium)

利用LCS求解

题目描述
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例
输入: “sea”, “eat”
输出: 2
解释: 第一步将”sea”变为”ea”，第二步将”eat”变为”ea”
思路
转化为求最长子序列。

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         //转化为求最长公共子序列问题
  4.         int len1 = word1.length();
  5.         int len2 = word2.length();
  6.         int[][] dp = new int[len1+1][len2+1];
  8.         for(int i=1; i<len1+1; i++){
  9.             char w1 = word1.charAt(i-1);
  10.             for(int j=1; j<len2+1; j++){
  11.                 char w2 = word2.charAt(j-1);
  12.                 dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
  13.                 if(w1==w2){
  14.                     dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
  15.                 }
  16.             }
  17.         }
  19.         return len1+len2-2*dp[len1][len2];
  20.     }
  21. }

普通动态规划求解

思路
dp[i][j] 表示 s_1 串前 _i 个字符和 s_2 串前 _j 个字符匹配的最少删除次数。

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         //转化为求最长公共子序列问题
  4.         int len1 = word1.length();
  5.         int len2 = word2.length();
  6.         int[][] dp = new int[len1+1][len2+1];
  7.         //初始化
  8.         for(int i=0; i<len1+1; i++){
  9.             dp[i][0] = i; 
  10.         }
  11.         for(int j=0; j<len2+1; j++){
  12.             dp[0][j] = j;
  13.         }
  14.         for(int i=1; i<len1+1; i++){
  15.             char w1 = word1.charAt(i-1);
  16.             for(int j=1; j<len2+1; j++){
  17.                 char w2 = word2.charAt(j-1);
  18.                 if(w1==w2){
  19.                     dp[i][j] = dp[i-1][j-1];
  20.                 }else{
  21.                     dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j])+1;
  22.                 }
  23.             }
  24.         }
  26.         return dp[len1][len2];
  27.     }
  28. }

上一种方法的内存优化

  1. public class Solution {
  2.     public int minDistance(String s1, String s2) {
  3.         int[] dp = new int[s2.length() + 1];
  4.         for (int i = 0; i <= s1.length(); i++) {
  5.             int[] temp=new int[s2.length()+1];
  6.             for (int j = 0; j <= s2.length(); j++) {
  7.                 if (i == 0 || j == 0)
  8.                     temp[j] = i + j;
  9.                 else if (s1.charAt(i - 1) == s2.charAt(j - 1))
  10.                     temp[j] = dp[j - 1];
  11.                 else
  12.                     temp[j] = 1 + Math.min(dp[j], temp[j - 1]);
  13.             }
  14.             dp=temp;
  15.         }
  16.         return dp[s2.length()];
  17.     }
  18. }

72. Edit Distance (Hard)

题目描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
思路

  • 对单词A删除，与对单词B插入是等价的

这样以来，本质不同的操作实际上为：

  • 在单词 A 中插入一个字符；
  • 在单词 B 中插入一个字符；
  • 修改单词 A 的一个字符。

这样以来，我们就可以把原问题转化为规模较小的子问题。我们用 A = horse，B = ros 作为例子，来看一看是如何把这个问题转化为规模较小的若干子问题的。

  • 在单词 A 中插入一个字符：如果我们知道 horse 到 ro 的编辑距离为 a，那么显然 horse 到 ros 的编辑距离不会超过 a + 1。这是因为我们可以在 a 次操作后将 horse 和 ro 变为相同的字符串，只需要额外的 1 次操作，在单词 A 的末尾添加字符 s，就能在 a + 1 次操作后将 horse 和 ro 变为相同的字符串；
  • 在单词 B 中插入一个字符：如果我们知道 hors 到 ros 的编辑距离为 b，那么显然 horse 到 ros 的编辑距离不会超过 b + 1，原因同上；
  • 修改单词 A 的一个字符：如果我们知道 hors 到 ro 的编辑距离为 c，那么显然 horse 到 ros 的编辑距离不会超过 c + 1，原因同上。

那么从 horse 变成 ros 的编辑距离应该为 min(a + 1, b + 1, c + 1)。

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         int len1 = word1.length();
  4.         int len2 = word2.length();
  5.         int[][] dp = new int [len1+1][len2+1];
  6.         //初始化
  7.         for(int i=0; i<len1+1; i++){
  8.             for(int j=0; j<len2+1; j++){
  9.                 if(i==0 || j==0){
  10.                     dp[i][j] = i+j;
  11.                 }else{
  12.                     char w1 = word1.charAt(i-1);
  13.                     char w2 = word2.charAt(j-1);
  14.                     if(w1==w2){
  15.                         dp[i][j] = dp[i-1][j-1];
  16.                     }else{
  17.                         dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
  18.                     }
  19.                 }
  20.             }
  21.         }
  22.         return dp[len1][len2];
  23.     }
  24. }

650. 2 Keys Keyboard (Medium)

题目描述
最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：
Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。
示例
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 ‘A’。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 ‘AA’。
第 3 步, 我们使用 Paste 操作来获得 ‘AAA’。
思路

  • 如果n为一个质数，那么结果就是n,因为只能一个个粘贴。
  • 如果n为一个合数，那么他的结果就是分解因式的结果之和.
    1. public int minSteps(int n) {
    2.   int[] dp = new int[n + 1];
    3.   int h = (int) Math.sqrt(n);
    4.   for (int i = 2; i <= n; i++) {
    5.       dp[i] = i;
    6.       for (int j = 2; j <= h; j++) {
    7.           if (i % j == 0) {
    8.               dp[i] = dp[j] + dp[i / j];
    9.               break;
    10.           }
    11.       }
    12.   }
    13.   return dp[n];
    14. }
    结果
    image.png