Reference: Link

583. Delete Operation for Two Strings (Medium)

My first idea is to use longest common string to solve this problem. At first, we find the longest common string, and then we calculate how many steps we need to delete these two strings to the target string.

But the most effective way is to use dp. dp[m][n] means how many steps required to make word1 and word2 the same. m and n are the index of two strings. There are two cases:

  1. word1[i] = word2[j]. If the current two characters are same, we don’t need to delete any one, so the result is same as dp[i-1][j-1].

  2. word1[i] != word2[j]. If the current two characters are different, we need to delete either the current character of s1 or s2. Thus, we need to plus 1 to the steps. The two options available at this moment are dp[i−1][j] and dp[i][j−1]. Since, we are keeping track of the minimum number of deletions required, we pick up the minimum out of these two values.

Since we only needs data from dp[i-1], we can use 1D array to represent 2D array. We also need a temp array to record value. And initial values are i or j.

Space complexity is O(m) or O(n). Time complexity is O(m+n). Here is the link.

    class Solution {
        public int minDistance(String word1, String word2) {
            int[]dp = new int[word1.length()+1];
            for(int i = 0;i<=word2.length();i++){
                int []temp = new int[word1.length()+1];
                for(int j =0;j<=word1.length();j++){
                    if(i==0||j==0){
                        temp[j] = i+j;
                    }
                    else if(word2.charAt(i-1)==word1.charAt(j-1)){
                        temp[j] = dp[j-1];
                    }
                    else{
                        temp[j] = Math.min(dp[j],temp[j-1])+1;
                    }
                }
                dp = temp;
            }
            return dp[dp.length-1];
        }
    }

72. Edit Distance (Hard)

This problem is similar to the last problem. In this problem, we have three options: insert, delete or replace. We are gonna to use delete and replace. I don’t use insert because it can be done by using delete. Thus, we simplify this problem to two options: delete or replace.

We still use dp to solve this problem. dp[i][j] means how many steps we need to make two strings same. The solution is very similar to the last problem. We only have a new option: replace. Thus, except delete one of character, we can replace one with the other one. And the result will be dp[i-1][j-1]+1. so we need to find the minimum steps between dp[i-1][j-1] and dp[i][j-1] and dp[i-1][j].

Time complexity is O(m+n). Space complexity is O(m) or O(n). Here is the link.

        public int minDistance(String word1, String word2) {
            int []dp = new int[word2.length()+1];
            for(int i =0;i<=word1.length();i++){
                int []temp = new int[word2.length()+1];
                for(int j =0;j<=word2.length();j++){
                    if(i==0||j==0){
                        temp[j] = i+j;
                    }
                    else if(word1.charAt(i-1)==word2.charAt(j-1)){
                        temp[j] = dp[j-1];
                    }
                    else{
                        temp[j] = Math.min(dp[j-1],Math.min(dp[j],temp[j-1]))+1;
                    }
                }
                dp = temp;
            }
            return dp[word2.length()];
        }

650. 2 Keys Keyboard (Medium)

This problem can be solved by dp or recursion. At first we need to find the rule of this problem. When n=1, we need to return 0. When n=2, we need to return 2 because we need to copy once and paste once. When n=3, we need to return 3 because of 1 copy and two pastes. When n=4, we need 4 steps: copy->paste->copy->paste or copy->paste->paste->paste. When n=5, we need 5 steps because of 1 copy and 4 pastes. When n=6, we need 5 steps because of copy->paste->copy->paste->paste or copy->paste->paste->copy->paste. Therefore, we know that we need to check all factors of n. If n%i==0, this means we can copy and paste a substring and its length is i. After copy this substring we need to paste it n/i-1 times, so there are n/i steps to copy and paste this substring. For each value n, there are at most n steps.

Use recursion to solve this problem:

    class Solution {
        public int minSteps(int n) {
            int ans = n;
            if(n==1)return 0;
            for(int i =2;i<n/2+1;i++){
                if(n%i==0){
                    int ope= 0;
                    if(i==1)ope=n/i-1;
                    else ope = n/i;
                    ans = Math.min(ans, i+minSteps(n/i));
                }
            }
            return ans;
        }
    }

Use dynamical programming to solve this problem:

    class Solution {
        public int minSteps(int n) {
            if(n==1)return 0;
            int[]dp = new int[n+1];
            for(int i =2;i<n+1;i++){
                dp[i]=i;
                for(int j= 2;j<n/2+1;j++){
                    if(i%j==0){
                        dp[i] = Math.min(dp[i],dp[j]+i/j);
                    }
                }
            }
            return dp[n];
        }
    }

Space complexity is O(n). Time complexity is O(n^2). Here is the link.