Дадени са два низа s1 и s2 . Задачата е да премахване/изтриване и вмъкнете на минимален брой знаци от s1 да го трансформирате в s2 . Възможно е, че същия характер трябва да бъде премахнат/изтрит от една точка на s1 и се вмъква в друга точка.
Пример 1:
вход: s1 = 'купчина' s2 =
Изход: 3
Обяснение: Минимално изтриване = 2 и минимално вмъкване = 1
p и h се изтриват от купчината и след това p се вмъква в началото. Едно нещо, което трябва да се отбележи, въпреки че p беше необходимо, първо беше премахнато/изтрито от позицията си и след това беше вмъкнато в друга позиция. Така p допринася едно за броя на изтриванията и едно за броя на вмъкванията.вход: s1 = 'geeksforgeeks' s2 = 'geeks'
Изход: 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) пространство
C++Един прост подход за решаване на проблема включва генериране на всички подпоследователности на s1 и за всяка подпоследователност изчисляване на минимум изтривания и вмъквания, необходими за трансформирането му в s2. Един ефективен подход използва концепцията за най-дълга обща подпоследователност (LCS) за да намерите дължината на най-дългия LCS. След като имаме LCS от два низа, можем да намерим Минимално вмъкване и Изтривания за преобразуване на s1 в s2.
- до минимизиране на изтриванията трябва само да премахнем символи от s1 които не са част от най-дълга обща подпоследователност (LCS) с s2 . Това може да се определи от изваждане на LCS дължина от дължината на s1 . Следователно минималният брой изтривания е:
minDeletions = дължина на s1 - LCS дължина.- Подобно на минимизиране на вмъкванията трябва само да вмъкнем знаци от s2 в s1 които не са част от LCS. Това може да се определи от изваждане на LCS дължина от дължината на s2 . Следователно минималният брой вмъквания е:
minInsertions = дължина на s2 - LCS дължина.
// C++ program to find the minimum number of insertion and deletion // using recursion. #include
// 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 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 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);
Изход
5
Използване на DP отгоре надолу (мемоизация) - O(n^2) време и O(n^2) пространство
C++В този подход прилагаме запомняне за съхраняване на резултатите от припокриващи се подпроблеми при намиране на най-дългата обща подпоследователност (LCS). А 2D масив бележка се използва за запазване на LCS дължини за различни поднизове на двата входни низа, като се гарантира, че всеки подпроблем се решава само веднъж.
Този метод е подобен на Най-дълга обща подпоследователност (LCS) проблем с използването на мемоизация.
// C++ program to find the minimum of insertion and deletion // using memoization. #include
// 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 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 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);
Изход
5
Използване на DP отдолу нагоре (табулиране) - O(n^2) време и O(n^2) пространство
C++Подходът е подобен на предишен просто вместо да разбиете проблема рекурсивно ние итеративно изградете решението, като пресмятате в отдолу нагоре начин. Ние поддържаме a 2D dp[][] таблица така че dp[i][j] съхранява Най-дълга обща подпоследователност (LCS) за подпроблем(i j) .
Този подход е подобен на намирането LCS по начин отдолу нагоре .
// C++ program to find the minimum of insertion and deletion // using tabulation. #include
// 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 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 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);
Изход
5
Използване на DP отдолу нагоре (оптимизиране на пространството) – O(n^2) време и O(n) пространство
C++В предишния подход на най-дълга обща подпоследователност (LCS) използва алгоритъм O(n * n) място за съхранение на целия dp маса . Тъй като обаче всяка стойност в dp[i][j ] зависи само от текущия ред и на предишния ред не е необходимо да съхраняваме цялата таблица. Това може да се оптимизира чрез съхраняване само на текущия и предишния ред. За повече подробности вижте Оптимизирано пространство решение на LCS .
// C++ program to find the minimum of insertion and deletion // using space optimized. #include
// 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 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 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);
Изход
5Създаване на тест