ある文字列を別の文字列に変換するための削除と挿入の最小数

2 つの文字列が与えられた場合 s1 そして s2 。課題は次のとおりです 削除/削除 そして 入れる の 最小文字数 から s1 それを変換する s2 。可能性としては、 同じキャラクター の 1 つのポイントから削除/削除する必要があります。 s1 そして別の場所に挿入されました。

例 1:

入力： s1 = 'ヒープ' s2 =
出力： 3
説明： 最小削除 = 2 および最小挿入 = 1
p と h がヒープから削除され、先頭に p が挿入されます。 p が必要であったにもかかわらず、最初にその位置から削除または削除されてから、別の位置に挿入されたことに注意する必要があります。したがって、p は削除カウントに 1 つ寄与し、挿入カウントに 1 つ寄与します。

入力： s1 = 'オタクフォーギーク' s2 = 'オタク'
出力： 8
説明： 8 個の削除、つまり文字列「forgeeks」のすべての文字を削除します。

再帰の使用 - O(2^n) 時間と O(n) 空間
トップダウン DP (メモ化) の使用 - O(n^2) 時間と O(n^2) 空間
ボトムアップ DP (表作成) の使用 - O(n^2) 時間と O(n^2) 空間
ボトムアップ DP (空間最適化) の使用 – O(n^2) 時間と O(n) 空間

再帰の使用 - O(2^n) 時間と O(n) 空間

問題を解決する簡単なアプローチには、すべてを生成することが含まれます。サブシーケンス s1 の各サブシーケンスについて、最小 s2 に変換するには削除と挿入が必要です。効率的なアプローチでは、次の概念が使用されます。 最長共通部分列 (LCS) 最長の LCS の長さを見つけます。 2 つの文字列の LCS が得られたら、次のことを見つけることができます。 最小挿入量 そして削除 s1 を s2 に変換します。
に 削除を最小限に抑える から文字を削除するだけで済みます s1 の一部ではないもの 最長共通部分列 (LCS) と s2 。これは次のように判断できます。 引き算 の LCSの長さ の長さから s1 。したがって、最小削除数は次のようになります。
minDeletions = s1 の長さ - LCS の長さ。
同様に 挿入を最小限に抑える から文字を挿入するだけです s2 の中へ s1 LCS の一部ではありません。これは次のように判断できます。 引き算 の LCSの長さ の長さから s2 。したがって、最小挿入数は次のようになります。
minInsertions = s2 の長さ - LCS の長さ。

C++

// C++ program to find the minimum number of insertion and deletion // using recursion. #include    using namespace std; int lcs(string &s1 string &s2 int m int n) {    // Base case: If either string is empty  // the LCS length is 0  if (m == 0 || n == 0)  return 0;  // If the last characters of both substrings match  if (s1[m - 1] == s2[n - 1])  // Include the matching character in LCS and   // recurse for remaining substrings  return 1 + lcs(s1 s2 m - 1 n - 1);  else  // If the last characters do not match   // find the maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  return max(lcs(s1 s2 m n - 1) lcs(s1 s2 m - 1 n)); } int minOperations(string s1 string s2) {  int m = s1.size();  int n = s2.size();  // the length of the LCS for s1[0..m-1]  // and s2[0..n-1]  int len = lcs(s1 s2 m n);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s1  int minInsertions = n - len;  // Total operations needed  int total = minDeletions + minInsertions;  return total; } int main() {  string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  cout << res;  return 0; }

Java

// Java program to find the minimum number of insertions and // deletions using recursion. class GfG {    static int lcs(String s1 String s2 int m int n) {    // Base case: If either string is empty the LCS  // length is 0  if (m == 0 || n == 0) {  return 0;  }  // If the last characters of both substrings match  if (s1.charAt(m - 1) == s2.charAt(n - 1)) {  // Include the matching character in LCS  // and recurse for remaining substrings  return 1 + lcs(s1 s2 m - 1 n - 1);  }  else {    // If the last characters do not match  // find the maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  return Math.max(lcs(s1 s2 m n - 1)  lcs(s1 s2 m - 1 n));  }  }  static int minOperations(String s1 String s2) {  int m = s1.length();  int n = s2.length();  // the length of LCS for s1[0..m-1] and  // s2[0..n-1]  int len = lcs(s1 s2 m n);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s2  int minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions;  }  public static void main(String[] args) {  String s1 = 'AGGTAB';  String s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  System.out.println(res);  } }

Python

# Python program to find the minimum number of insertions # and deletions using recursion def lcs(s1 s2 m n): # Base case: If either string is empty # the LCS length is 0 if m == 0 or n == 0: return 0 # If the last characters of both substrings match if s1[m - 1] == s2[n - 1]: # Include the matching character in LCS and  # recurse for remaining substrings return 1 + lcs(s1 s2 m - 1 n - 1) else: # If the last characters do not match  # find the maximum LCS length by: # 1. Excluding the last character of s1 # 2. Excluding the last character of s2 return max(lcs(s1 s2 m n - 1) lcs(s1 s2 m - 1 n)) def minOperations(s1 s2): m = len(s1) n = len(s2) # the length of LCS for s1[0..m-1] and s2[0..n-1] lengthLcs = lcs(s1 s2 m n) # Characters to delete from str1 minDeletions = m - lengthLcs # Characters to insert into str1 minInsertions = n - lengthLcs # Total operations needed return minDeletions + minInsertions if __name__ == '__main__': s1 = 'AGGTAB' s2 = 'GXTXAYB' result = minOperations(s1 s2) print(result)

// C# program to find the minimum number of insertions and // deletions using recursion. using System; class GfG {  static int lcs(string s1 string s2 int m int n) {    // Base case: If either string is empty the LCS  // length is 0  if (m == 0 || n == 0)  return 0;  // If the last characters of both substrings match  if (s1[m - 1] == s2[n - 1]) {    // Include the matching character in LCS  // and recurse for remaining substrings  return 1 + lcs(s1 s2 m - 1 n - 1);  }  else {    // If the last characters do not match  // find the maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  return Math.Max(lcs(s1 s2 m n - 1)  lcs(s1 s2 m - 1 n));  }  }  static int minOperations(string s1 string s2) {  int m = s1.Length;  int n = s2.Length;  // the length of LCS for s1[0..m-1] and  // s2[0..n-1]  int lengthLcs = lcs(s1 s2 m n);  // Characters to delete from s1  int minDeletions = m - lengthLcs;  // Characters to insert into s2  int minInsertions = n - lengthLcs;  // Total operations needed  return minDeletions + minInsertions;  }  static void Main(string[] args) {  string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int result = minOperations(s1 s2);  Console.WriteLine(result);  } }

JavaScript

// JavaScript program to find the minimum number of // insertions and deletions using recursion function lcs(s1 s2 m n) {  // Base case: If either string is empty the LCS length  // is 0  if (m === 0 || n === 0) {  return 0;  }  // If the last characters of both substrings match  if (s1[m - 1] === s2[n - 1]) {    // Include the matching character in LCS and recurse  // for remaining substrings  return 1 + lcs(s1 s2 m - 1 n - 1);  }  else {    // If the last characters do not match find the  // maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  return Math.max(lcs(s1 s2 m n - 1)  lcs(s1 s2 m - 1 n));  } } function minOperations(s1 s2) {  const m = s1.length;  const n = s2.length;  // Length of the LCS  const len = lcs(s1 s2 m n);  // Characters to delete from s1  const minDeletions = m - len;  // Characters to insert into s1  const minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions; } const s1 = 'AGGTAB'; const s2 = 'GXTXAYB'; const res = minOperations(s1 s2); console.log(res);

出力

トップダウン DP (メモ化) の使用 - O(n^2) 時間と O(n^2) 空間

このアプローチでは、 メモ化 最長共通部分列 (LCS) を見つけながら、重複する部分問題の結果を保存します。あ 2次元配列 メモを保存するために使用されます LCS 2 つの入力文字列の異なる部分文字列の長さを計算し、各部分問題が 1 回だけ解決されるようにします。
この方法は次のようなものです最長共通部分列 (LCS) メモ化の使用に関する問題。

C++

// C++ program to find the minimum of insertion and deletion // using memoization. #include    #include  using namespace std; int lcs(string &s1 string &s2 int m int n   vector<vector<int>> &memo) {    // Base case: If either string is empty the LCS length is 0  if (m == 0 || n == 0)  return 0;  // If the value is already computed return  // it from the memo array  if(memo[m][n]!=-1)  return memo[m][n];    // If the last characters of both substrings match  if (s1[m - 1] == s2[n - 1])    // Include the matching character in LCS and recurse for  // remaining substrings  return memo[m][n] = 1 + lcs(s1 s2 m - 1 n - 1 memo);  else    // If the last characters do not match find the maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  return memo[m][n] = max(lcs(s1 s2 m n - 1 memo)  lcs(s1 s2 m - 1 n memo)); } int minOperations(string s1 string s2) {    int m = s1.size();   int n = s2.size();     // Initialize the memoization array with -1.  vector<vector<int>> memo = vector<vector<int>>  (m+1vector<int>(n+1-1));    // the length of the LCS for   // s1[0..m-1] and s2[0..n-1]  int len = lcs(s1 s2 m n memo);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s1  int minInsertions = n - len;  // Total operations needed  int total = minDeletions + minInsertions;  return total; } int main() {    string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  cout << res;  return 0; }

Java

// Java program to find the minimum of insertion and deletion // using memoization. class GfG {  static int lcs(String s1 String s2 int m int n int[][] memo) {    // Base case: If either string is empty   // the LCS length is 0  if (m == 0 || n == 0) {   return 0;  }  // If the value is already computed return it  // from the memo array  if (memo[m][n] != -1) {  return memo[m][n];  }  // If the last characters of both substrings match  if (s1.charAt(m - 1) == s2.charAt(n - 1)) {  // Include the matching character in LCS and recurse for  // remaining substrings  memo[m][n] = 1 + lcs(s1 s2 m - 1 n - 1 memo);  }  else {    // If the last characters do not match  // find the maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  memo[m][n] = Math.max(lcs(s1 s2 m n - 1 memo)  lcs(s1 s2 m - 1 n memo));  }  return memo[m][n];  }  static int minOperations(String s1 String s2) {    int m = s1.length();   int n = s2.length();   // Initialize the memoization array with -1   // (indicating uncalculated values)  int[][] memo = new int[m + 1][n + 1];  for (int i = 0; i <= m; i++) {  for (int j = 0; j <= n; j++) {  memo[i][j] = -1;  }  }  // the length of LCS for s1[0..m-1] and s2[0..n-1]  int len = lcs(s1 s2 m n memo);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s1  int minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions;  }  static void main(String[] args) {    String s1 = 'AGGTAB';   String s2 = 'GXTXAYB';   int res = minOperations(s1 s2);   System.out.println(res);   } }

Python

# Python program to find the minimum number of insertions and  # deletions using memoization def lcs(s1 s2 m n memo): # Base case: If either string is empty the LCS length is 0 if m == 0 or n == 0: return 0 # If the value is already computed  # return it from the memo array if memo[m][n] != -1: return memo[m][n] # If the last characters of both substrings match if s1[m - 1] == s2[n - 1]: # Include the matching character in LCS and  # recurse for remaining substrings memo[m][n] = 1 + lcs(s1 s2 m - 1 n - 1 memo) else: # If the last characters do not match  # find the maximum LCS length by: # 1. Excluding the last character of s1 # 2. Excluding the last character of s2 memo[m][n] = max(lcs(s1 s2 m n - 1 memo) lcs(s1 s2 m - 1 n memo)) # Return the computed value return memo[m][n] def minOperations(s1 s2): m = len(s1) n = len(s2) # Initialize the memoization array with -1 # (indicating uncalculated values) memo = [[-1 for _ in range(n + 1)] for _ in range(m + 1)] # Calculate the length of LCS for s1[0..m-1] and s2[0..n-1] lengthLcs = lcs(s1 s2 m n memo) # Characters to delete from s1 minDeletions = m - lengthLcs # Characters to insert into s1 minInsertions = n - lengthLcs # Total operations needed return minDeletions + minInsertions if __name__ == '__main__': s1 = 'AGGTAB' s2 = 'GXTXAYB' res = minOperations(s1 s2) print(res)

// C# program to find the minimum of insertion and deletion // using memoization. using System; class GfG {    static int lcs(string s1 string s2 int m int n  int[ ] memo) {    // Base case: If either string is empty the LCS  // length is 0  if (m == 0 || n == 0) {  return 0;  }  // If the value is already computed return it from  // the memo array  if (memo[m n] != -1) {  return memo[m n];  }  // If the last characters of both substrings match  if (s1[m - 1] == s2[n - 1]) {    // Include the matching character in LCS and  // recurse for remaining substrings  memo[m n]  = 1 + lcs(s1 s2 m - 1 n - 1 memo);  }  else {    // If the last characters do not match find the  // maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  memo[m n]  = Math.Max(lcs(s1 s2 m n - 1 memo)  lcs(s1 s2 m - 1 n memo));  }  // Return the computed value  return memo[m n];  }    static int minOperations(string s1 string s2) {    int m = s1.Length;   int n = s2.Length;   // Initialize the memoization array with -1  // (indicating uncalculated values)  int[ ] memo = new int[m + 1 n + 1];  for (int i = 0; i <= m; i++) {  for (int j = 0; j <= n; j++) {  memo[i j] = -1;  }  }  // Calculate the length of LCS for s1[0..m-1] and  // s2[0..n-1]  int lengthLcs = lcs(s1 s2 m n memo);  // Characters to delete from s1  int minDeletions = m - lengthLcs;  // Characters to insert into s1  int minInsertions = n - lengthLcs;  // Total operations needed  return minDeletions + minInsertions;  }    static void Main(string[] args) {    string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  Console.WriteLine(res);   } }

JavaScript

// JavaScript program to find the minimum number of // insertions and deletions using memoization function lcs(s1 s2 m n memo) {  // Base case: If either string is empty the LCS length  // is 0  if (m === 0 || n === 0) {  return 0;  }  // If the value is already computed return it from the  // memo array  if (memo[m][n] !== -1) {  return memo[m][n];  }  // If the last characters of both substrings match  if (s1[m - 1] === s2[n - 1]) {    // Include the matching character in LCS and recurse  // for remaining substrings  memo[m][n] = 1 + lcs(s1 s2 m - 1 n - 1 memo);  }  else {    // If the last characters do not match find the  // maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  memo[m][n] = Math.max(lcs(s1 s2 m n - 1 memo)  lcs(s1 s2 m - 1 n memo));  }    return memo[m][n]; } function minOperations(s1 s2){  const m = s1.length;  const n = s2.length;  // Initialize the memoization array with -1 (indicating  // uncalculated values)  const memo = Array.from({length : m + 1}  () => Array(n + 1).fill(-1));  // Calculate the length of LCS for s1[0..m-1] and  // s2[0..n-1]  const len = lcs(s1 s2 m n memo);  // Characters to delete from s1  const minDeletions = m - len;  // Characters to insert into s1  const minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions; } const s1 = 'AGGTAB'; const s2 = 'GXTXAYB'; const res = minOperations(s1 s2); console.log(res);

出力

ボトムアップ DP (表作成) の使用 - O(n^2) 時間と O(n^2) 空間

アプローチは次のようなものです 前のやつ 問題を分解するのではなく 再帰的に 私たちは 繰り返し で計算して解を構築する ボトムアップ やり方。私たちは、 2D dp[][] テーブル dp[i][j] には 最長共通部分列 (LCS) のために 部分問題(i j) 。
このアプローチは、検索に似ています。ボトムアップ方式の LCS 。

C++

// C++ program to find the minimum of insertion and deletion // using tabulation. #include    #include  using namespace std;   int lcs(string &s1 string &s2) {    int m = s1.size();  int n = s2.size();  // Initializing a matrix of size (m+1)*(n+1)  vector<vector<int>> dp(m + 1 vector<int>(n + 1 0));  // Building dp[m+1][n+1] in bottom-up fashion  for (int i = 1; i <= m; ++i) {  for (int j = 1; j <= n; ++j) {  if (s1[i - 1] == s2[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;  else  dp[i][j] = max(dp[i - 1][j] dp[i][j - 1]);  }  }  // dp[m][n] contains length of LCS for s1[0..m-1]  // and s2[0..n-1]  return dp[m][n]; } int minOperations(string s1 string s2) {    int m = s1.size();  int n = s2.size();  // the length of the LCS for  // s1[0..m-1] and s2[0..n-1]  int len = lcs(s1 s2);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s1  int minInsertions = n - len;  // Total operations needed  int total = minDeletions + minInsertions;  return total; } int main() {    string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  cout << res;  return 0; }

Java

// Java program to find the minimum of insertion and // deletion using tabulation. class GfG {    static int lcs(String s1 String s2) {    int m = s1.length();  int n = s2.length();  // Initializing a matrix of size (m+1)*(n+1)  int[][] dp = new int[m + 1][n + 1];  // Building dp[m+1][n+1] in bottom-up fashion  for (int i = 1; i <= m; ++i) {  for (int j = 1; j <= n; ++j) {  if (s1.charAt(i - 1) == s2.charAt(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]);  }  }  // dp[m][n] contains length of LCS for s1[0..m-1]  // and s2[0..n-1]  return dp[m][n];  }  static int minOperations(String s1 String s2) {    int m = s1.length();  int n = s2.length();  // the length of the LCS for s1[0..m-1] and  // str2[0..n-1]  int len = lcs(s1 s2);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s1  int minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions;  }  public static void main(String[] args) {    String s1 = 'AGGTAB';  String s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  System.out.println(res);  } }

Python

# Python program to find the minimum of insertion and deletion # using tabulation. def lcs(s1 s2): m = len(s1) n = len(s2) # Initializing a matrix of size (m+1)*(n+1) dp = [[0] * (n + 1) for _ in range(m + 1)] # Building dp[m+1][n+1] in bottom-up fashion for i in range(1 m + 1): for j in range(1 n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j] dp[i][j - 1]) # dp[m][n] contains length of LCS for # s1[0..m-1] and s2[0..n-1] return dp[m][n] def minOperations(s1 s2): m = len(s1) n = len(s2) # the length of the LCS for  # s1[0..m-1] and s2[0..n-1] lengthLcs = lcs(s1 s2) # Characters to delete from s1 minDeletions = m - lengthLcs # Characters to insert into s1 minInsertions = n - lengthLcs # Total operations needed return minDeletions + minInsertions s1 = 'AGGTAB' s2 = 'GXTXAYB' res = minOperations(s1 s2) print(res)

// C# program to find the minimum of insertion and deletion // using tabulation. using System; class GfG {    static int Lcs(string s1 string s2) {    int m = s1.Length;  int n = s2.Length;  // Initializing a matrix of size (m+1)*(n+1)  int[ ] dp = new int[m + 1 n + 1];  // Building dp[m+1][n+1] in bottom-up fashion  for (int i = 1; i <= m; ++i) {  for (int j = 1; j <= n; ++j) {  if (s1[i - 1] == s2[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]);  }  }  // dp[m n] contains length of LCS for s1[0..m-1]  // and s2[0..n-1]  return dp[m n];  }  static int minOperations(string s1 string s2) {    int m = s1.Length;  int n = s2.Length;  // the length of the LCS for s1[0..m-1] and  // s2[0..n-1]  int len = Lcs(s1 s2);  // Characters to delete from str1  int minDeletions = m - len;  // Characters to insert into str1  int minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions;  }  static void Main() {    string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  Console.WriteLine(res);  } }

JavaScript

// JavaScript program to find the minimum of insertion and // deletion using tabulation. function lcs(s1 s2) {  let m = s1.length;  let n = s2.length;  // Initializing a matrix of size (m+1)*(n+1)  let dp = Array(m + 1).fill().map(  () => Array(n + 1).fill(0));  // Building dp[m+1][n+1] in bottom-up fashion  for (let i = 1; i <= m; ++i) {  for (let j = 1; j <= n; ++j) {  if (s1[i - 1] === s2[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]);  }  }  // dp[m][n] contains length of LCS for s1[0..m-1] and  // s2[0..n-1]  return dp[m][n]; } function minOperations(s1 s2) {  let m = s1.length;  let n = s2.length;  // the length of the LCS for s1[0..m-1] and s2[0..n-1]  let len = lcs(s1 s2);  // Characters to delete from s1  let minDeletions = m - len;  // Characters to insert into s1  let minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions; } let s1 = 'AGGTAB'; let s2 = 'GXTXAYB'; let res = minOperations(s1 s2); console.log(res);

出力

ボトムアップ DP (空間最適化) の使用 – O(n^2) 時間と O(n) 空間

前のアプローチでは、 最長共通部分列 (LCS) アルゴリズムが使用する O(n * n) 全体を収納できるスペース dpテーブル 。ただし、それぞれの値は dp[i][j ]にのみ依存します。 現在の行 そして 前の行 テーブル全体を保存する必要はありません。これは、現在行と前の行のみを保存することで最適化できます。詳細については、を参照してください。 LCS のスペース最適化ソリューション。

C++

// C++ program to find the minimum of insertion and deletion // using space optimized. #include    using namespace std; int lcs(string &s1 string &s2) {    int m = s1.length() n = s2.length();  vector<vector<int>> dp(2 vector<int>(n + 1));  for (int i = 0; i <= m; i++) {  // Compute current binary index. If i is even  // then curr = 0 else 1  bool curr = i & 1;  for (int j = 0; j <= n; j++) {    // Initialize first row and first column with 0  if (i == 0 || j == 0)  dp[curr][j] = 0;  else if (s1[i - 1] == s2[j - 1])  dp[curr][j] = dp[1 - curr][j - 1] + 1;  else  dp[curr][j] = max(dp[1 - curr][j] dp[curr][j - 1]);  }  }  return dp[m & 1][n]; } int minOperations(string s1 string s2) {  int m = s1.size();  int n = s2.size();  // the length of the LCS for s1[0..m-1] and s2[0..n-1]  int len = lcs(s1 s2);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s1  int minInsertions = n - len;  // Total operations needed  int total = minDeletions + minInsertions;  return total; } int main() {  string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  cout << res;  return 0; }

Java

// Java program to find the minimum of insertion and // deletion using space optimized. class GfG {    static int lcs(String s1 String s2) {    int m = s1.length();  int n = s2.length();  // Initializing a 2D array with size (2) x (n + 1)  int[][] dp = new int[2][n + 1];  for (int i = 0; i <= m; i++) {  // Compute current binary index. If i is even  // then curr = 0 else 1  int curr = i % 2;  for (int j = 0; j <= n; j++) {    // Initialize first row and first column  // with 0  if (i == 0 || j == 0)  dp[curr][j] = 0;  else if (s1.charAt(i - 1)  == s2.charAt(j - 1))  dp[curr][j] = dp[1 - curr][j - 1] + 1;  else  dp[curr][j] = Math.max(dp[1 - curr][j]  dp[curr][j - 1]);  }  }  return dp[m % 2][n];  }  static int minOperations(String s1 String s2) {    int m = s1.length();  int n = s2.length();  // the length of the LCS for s1[0..m-1] and  // s2[0..n-1]  int len = lcs(s1 s2);  // Characters to delete from s1  int minDeletions = m - len;  // Characters to insert into s1  int minInsertions = n - len;  // Total operations needed  return minDeletions + minInsertions;  }  public static void main(String[] args) {    String s1 = 'AGGTAB';  String s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  System.out.println(res);  } }

Python

# Python program to find the minimum of insertion and deletion # using space optimized. def lcs(s1 s2): m = len(s1) n = len(s2) # Initializing a matrix of size (2)*(n+1) dp = [[0] * (n + 1) for _ in range(2)] for i in range(m + 1): # Compute current binary index. If i is even # then curr = 0 else 1 curr = i % 2 for j in range(n + 1): # Initialize first row and first column with 0 if i == 0 or j == 0: dp[curr][j] = 0 # If the last characters of both substrings match elif s1[i - 1] == s2[j - 1]: dp[curr][j] = dp[1 - curr][j - 1] + 1 # If the last characters do not match # find the maximum LCS length by: # 1. Excluding the last character of s1 # 2. Excluding the last character of s2 else: dp[curr][j] = max(dp[1 - curr][j] dp[curr][j - 1]) # dp[m & 1][n] contains length of LCS for s1[0..m-1] and s2[0..n-1] return dp[m % 2][n] def minOperations(s1 s2): m = len(s1) n = len(s2) # the length of the LCS for s1[0..m-1] and s2[0..n-1] length = lcs(s1 s2) # Characters to delete from s1 minDeletions = m - length # Characters to insert into s1 minInsertions = n - length # Total operations needed return minDeletions + minInsertions s1 = 'AGGTAB' s2 = 'GXTXAYB' res = minOperations(s1 s2) print(res)

// C# program to find the minimum of insertion and deletion // using space optimized. using System; class GfG {  static int lcs(string s1 string s2) {    int m = s1.Length;  int n = s2.Length;  // Initializing a matrix of size (2)*(n+1)  int[][] dp = new int[2][];  dp[0] = new int[n + 1];  dp[1] = new int[n + 1];  for (int i = 0; i <= m; i++) {    // Compute current binary index. If i is even  // then curr = 0 else 1  int curr = i % 2;  for (int j = 0; j <= n; j++) {    // Initialize first row and first column  // with 0  if (i == 0 || j == 0)  dp[curr][j] = 0;  // If the last characters of both substrings  // match  else if (s1[i - 1] == s2[j - 1])  dp[curr][j] = dp[1 - curr][j - 1] + 1;  // If the last characters do not match  // find the maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  else  dp[curr][j] = Math.Max(dp[1 - curr][j]  dp[curr][j - 1]);  }  }  // dp[m & 1][n] contains length of LCS for  // s1[0..m-1] and s2[0..n-1]  return dp[m % 2][n];  }  static int minOperations(string s1 string s2) {    int m = s1.Length;  int n = s2.Length;  // the length of the LCS for s1[0..m-1] and  // s2[0..n-1]  int length = lcs(s1 s2);  // Characters to delete from s1  int minDeletions = m - length;  // Characters to insert into s1  int minInsertions = n - length;  // Total operations needed  return minDeletions + minInsertions;  }  static void Main(string[] args) {    string s1 = 'AGGTAB';  string s2 = 'GXTXAYB';  int res = minOperations(s1 s2);  Console.WriteLine(res);  } }

JavaScript

// JavaScript program to find the minimum of insertion and // deletion using space optimized. function lcs(s1 s2) {  const m = s1.length;  const n = s2.length;  // Initializing a matrix of size (2)*(n+1)  const dp  = Array(2).fill().map(() => Array(n + 1).fill(0));  for (let i = 0; i <= m; i++) {    // Compute current binary index. If i is even  // then curr = 0 else 1  const curr = i % 2;  for (let j = 0; j <= n; j++) {    // Initialize first row and first column with 0  if (i === 0 || j === 0)  dp[curr][j] = 0;  // If the last characters of both substrings  // match  else if (s1[i - 1] === s2[j - 1])  dp[curr][j] = dp[1 - curr][j - 1] + 1;  // If the last characters do not match  // find the maximum LCS length by:  // 1. Excluding the last character of s1  // 2. Excluding the last character of s2  else  dp[curr][j] = Math.max(dp[1 - curr][j]  dp[curr][j - 1]);  }  }  // dp[m & 1][n] contains length of LCS for s1[0..m-1]  // and s2[0..n-1]  return dp[m % 2][n]; } function minOperations(s1 s2) {  const m = s1.length;  const n = s2.length;  // the length of the LCS for s1[0..m-1] and s2[0..n-1]  const length = lcs(s1 s2);  // Characters to delete from s1  const minDeletions = m - length;  // Characters to insert into s1  const minInsertions = n - length;  // Total operations needed  return minDeletions + minInsertions; } const s1 = 'AGGTAB'; const s2 = 'GXTXAYB'; const res = minOperations(s1 s2); console.log(res);

出力

クイズの作成