Date due stringhe s1 E s2 . Il compito è quello rimuovere/eliminare E inserire IL numero minimo di caratteri da s1 per trasformarlo in s2 . Potrebbe essere possibile che il stesso personaggio deve essere rimosso/eliminato da un punto di s1 e inserito in un altro punto.
Esempio 1:
Ingresso: s1 = 'heap' s2 =
Produzione: 3
Spiegazione: Cancellazione minima = 2 e Inserimento minimo = 1
p e h vengono cancellati dall'heap e poi p viene inserito all'inizio. Una cosa da notare, sebbene p fosse richiesta, è stata rimossa/eliminata prima dalla sua posizione e poi è stata inserita in un'altra posizione. Pertanto p contribuisce con uno al conteggio delle cancellazioni e con uno al conteggio degli inserimenti.Ingresso: s1 = 'geeksforgeeks' s2 = 'geeks'
Produzione: 8
Spiegazione: 8 eliminazioni, ovvero rimuovi tutti i caratteri della stringa "forgeeks".
Sommario
- Utilizzo della ricorsione: tempo O(2^n) e spazio O(n).
- Utilizzo della DP (memoizzazione) top-down: tempo O(n^2) e spazio O(n^2).
- Utilizzo della DP (tabulazione) bottom-up: tempo O(n^2) e spazio O(n^2).
- Utilizzo della DP (ottimizzazione dello spazio) bottom-up: tempo O(n^2) e spazio O(n)
Utilizzo della ricorsione: tempo O(2^n) e spazio O(n).
C++Un approccio semplice per risolvere il problema prevede la generazione di tutti sottosequenze di s1 e per ogni sottosuccessione calcolando il minimo cancellazioni e inserimenti necessari per trasformarlo in s2. Un approccio efficace utilizza il concetto di sottosequenza comune più lunga (LCS) per trovare la lunghezza della LCS più lunga. Una volta che abbiamo LCS di due stringhe possiamo trovare Inserimento minimo E Eliminazioni per convertire s1 in s2.
- A ridurre al minimo le eliminazioni dobbiamo solo rimuovere i caratteri da s1 che non fanno parte del sottosequenza comune più lunga (LCS) con s2 . Questo può essere determinato da sottraendo IL Lunghezza LCS dalla lunghezza di s1 . Pertanto il numero minimo di eliminazioni è:
minDeletions = lunghezza di s1 - lunghezza LCS.- Allo stesso modo a ridurre al minimo gli inserimenti dobbiamo solo inserire i caratteri from s2 in s1 che non fanno parte della LCS. Questo può essere determinato da sottraendo IL Lunghezza LCS dalla lunghezza di s2 . Pertanto il numero minimo di inserimenti è:
minInserzioni = lunghezza di s2 - lunghezza 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);
Produzione
5
Utilizzo della DP (memoizzazione) top-down: tempo O(n^2) e spazio O(n^2).
C++In questo approccio applichiamo memorizzazione per memorizzare i risultati dei sottoproblemi sovrapposti trovando la sottosequenza comune più lunga (LCS). UN matrice 2D promemoria viene utilizzato per salvare il file LCS lunghezze per diverse sottostringhe delle due stringhe di input garantendo che ogni sottoproblema venga risolto una sola volta.
Questo metodo è simile a Sottosequenza comune più lunga (LCS) problema con la memorizzazione.
// 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);
Produzione
5
Utilizzo della DP (tabulazione) bottom-up: tempo O(n^2) e spazio O(n^2).
C++L'approccio è simile a quello precedente semplicemente invece di scomporre il problema ricorsivamente Noi iterativamente costruire la soluzione calcolando dal basso verso l'alto maniera. Manteniamo a Tabella dp[][] 2D tale che dp[i][j] memorizzi il Sottosequenza comune più lunga (LCS) per il sottoproblema(ij) .
Questo approccio è simile alla ricerca LCS in modalità bottom-up .
// 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);
Produzione
5
Utilizzo della DP (ottimizzazione dello spazio) bottom-up: tempo O(n^2) e spazio O(n)
C++Nell'approccio precedente il sottosequenza comune più lunga (LCS) l'algoritmo utilizza O(n*n) spazio per riporre l'intero tabella DP . Tuttavia, poiché ogni valore in dp[i][j ] dipende solo da riga corrente e il riga precedente non è necessario memorizzare l'intera tabella. Questo può essere ottimizzato memorizzando solo la riga corrente e quella precedente. Per maggiori dettagli fare riferimento a Una soluzione ottimizzata per lo spazio di 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);
Produzione
5Crea quiz