Задача:
Даны две строки str1 и str2. Задача состоит в том, чтобы удалить или вставить минимальное количество символов из строки 1, чтобы преобразовать ее в строку 2. Возможно, что один и тот же символ нужно удалить/убрать из одной точки строки str1 и вставить в другую точку.
Пример 1:
Input: str1 = "heap", str2 = "pea"
Output: 3
Решение:
Intuition : Find the largest common subsequence of the two strings and substract it from
the length of the two strings and finally add the subtractions. i.e. m+n - 2 *lcs(StringA, StringB)
Подход «снизу вверх» (мемоизация) :
Временная сложность: O(m*n), где m и n — длина двух строк a и b.
пространственная сложность: o(m*n) для использования 2d dp и O(m+n) для вспомогательного стекового пространства, поскольку в худшем случае мы будем делать m+n рекурсивных вызовов.
Проблема кодирования ниндзя
import java.util.*;
public class Solution {
public static int canYouMake(String str, String ptr) {
// Write your code here.
// we will use bottom up approach for solving this problem.
int dp[][] =new int[str.length()][ptr.length()];
for(int row[] : dp){
Arrays.fill(row,-1);
}
return str.length()+ptr.length() - 2 *lcs(str,ptr, str.length()-1, ptr.length()-1,dp);
}
public static int lcs(String str, String ptr, int m,int n,int dp[][]){
if(m<0 || n<0){
return 0;
}
if(dp[m][n]!=-1) return dp[m][n];
if(str.charAt(m)==ptr.charAt(n)){
dp[m][n] = 1 + lcs(str,ptr,m-1,n-1,dp);
}
else{
dp[m][n] = 0 + Integer.max(lcs(str,ptr,m-1,n,dp), lcs(str,ptr,m,n-1,dp));
}
return dp[m][n];
}
}
Подход сверху вниз (табуляция) :
Временная сложность : O(m*n), где m и n — длина двух строк a и b.
пространственная сложность : o(m*n) для использования 2d dp
GeeksForGeeksProblem
class Solution
{
public int minOperations(String str1, String str2)
{
// we will use top down approach to solve this
int dp[][] =new int[str1.length()+1][str2.length()+1];
for(int i =0;i<=str1.length();i++){
dp[i][0] = 0;
}
for(int i =0;i<=str2.length();i++){
dp[0][i] = 0;
}
for(int i =1;i<=str1.length();i++){
for(int j =1;j<=str2.length();j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
dp[i][j] = 1 + dp[i-1][j-1];
}
else dp[i][j] = Integer.max(dp[i-1][j],dp[i][j-1]);
}
}
return str1.length() + str2.length() - 2 * dp[str1.length()][str2.length()];
}
}