Dotas divas stīgas s1 un s2 . Uzdevums ir noņemt/dzēst un ievietot uz minimālais rakstzīmju skaits no s1 lai to pārveidotu par s2 . Varētu būt iespējams, ka tas pats raksturs ir jānoņem/jādzēš no viena punkta s1 un ievietots citā vietā.
1. piemērs:
Ievade: s1 = 'kaudze' s2 =
Izvade: 3
Paskaidrojums: Minimālā dzēšana = 2 un minimālā ievietošana = 1
p un h tiek dzēsti no kaudzes, un tad p tiek ievietots sākumā. Viena lieta, kas jāatzīmē, lai gan p bija nepieciešams, tas vispirms tika noņemts/izdzēsts no savas pozīcijas un pēc tam tika ievietots citā pozīcijā. Tādējādi p dod vienu ieguldījumu dzēšanas skaitā un vienu ievietošanas skaitā.Ievade: s1 = "geeksforgeeks" s2 = "geeks"
Izvade: 8
Paskaidrojums: 8 svītrojumi, t.i., noņemiet visas virknes "forgeeks" rakstzīmes.
Satura rādītājs
- Rekursijas izmantošana - O(2^n) laiks un O(n) telpa
- No augšas uz leju DP (atgādņu veidošana) izmantošana — O(n^2) laiks un O(n^2) telpa
- Augšupvērsto DP izmantošana (tabulēšana) — O(n^2) laiks un O(n^2) telpa
- Augšupvērsto DP izmantošana (telpas optimizācija) — O(n^2) laiks un O(n) telpa
Rekursijas izmantošana - O(2^n) laiks un O(n) telpa
C++Vienkārša pieeja problēmas risināšanai ietver visu ģenerēšanu sekvences s1 un katrai apakšsecībai, aprēķinot minimums svītrojumi un ievietojumi, kas nepieciešami, lai to pārveidotu par s2. Efektīva pieeja izmanto jēdzienu garākā kopīgā apakšsecība (LCS) lai atrastu garākā LCS garumu. Kad mums ir divu virkņu LCS, mēs varam atrast Minimālā ievietošana un Svītrojumi lai pārvērstu s1 par s2.
- Uz samazināt svītrojumus mums tikai jānoņem rakstzīmes no s1 kas nav daļa no garākā kopīgā apakšsecība (LCS) ar s2 . To var noteikt pēc atņemot uz LCS garums no garuma s1 . Tādējādi minimālais svītrojumu skaits ir:
minDzēšumi = s1 garums — LCS garums.- Līdzīgi kā samazināt ievietošanas iespējas mums ir jāievieto tikai rakstzīmes no s2 iekšā s1 kas neietilpst LCS. To var noteikt pēc atņemot uz LCS garums no garuma s2 . Tādējādi minimālais ievietošanas reižu skaits ir:
minInsertions = s2 garums — LCS garums.
// 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);
Izvade
5
No augšas uz leju DP (atgādņu veidošana) izmantošana — O(n^2) laiks un O(n^2) telpa
C++Šajā pieejā mēs izmantojam iegaumēšana lai saglabātu pārklājošu apakšproblēmu rezultātus, vienlaikus atrodot garāko kopējo apakšsekvenci (LCS). A 2D masīvs piezīme tiek izmantots, lai saglabātu LCS garumi dažādām divu ievades virkņu apakšvirknēm, nodrošinot, ka katra apakšproblēma tiek atrisināta tikai vienu reizi.
Šī metode ir līdzīga Garākā kopējā secība (LCS) problēma, izmantojot memoizāciju.
// 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);
Izvade
5
Augšupvērsto DP izmantošana (tabulēšana) — O(n^2) laiks un O(n^2) telpa
C++Pieeja ir līdzīga iepriekšējā tikai tā vietā, lai nojauktu problēmu rekursīvi mēs iteratīvi izveidojiet risinājumu, aprēķinot iekšā no apakšas uz augšu veidā. Mēs uzturam a 2D dp[][] tabula tā, lai dp[i][j] saglabātu Garākā kopējā secība (LCS) priekš apakšproblēma (i j) .
Šī pieeja ir līdzīga atrašanai LCS augšupējā veidā .
// 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);
Izvade
5
Augšupvērsto DP izmantošana (telpas optimizācija) — O(n^2) laiks un O(n) telpa
C++Iepriekšējā pieejā garākā kopīgā apakšsecība (LCS) algoritmu lietojumi O(n * n) vieta, kur uzglabāt visu dp tabula . Tomēr, tā kā katra vērtība in dp[i][j ] ir atkarīgs tikai no pašreizējā rinda un iepriekšējā rinda mums nav jāuzglabā viss galds. To var optimizēt, saglabājot tikai pašreizējās un iepriekšējās rindas. Sīkāku informāciju skatiet Kosmosam optimizēts LCS risinājums .
// 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);
Izvade
5Izveidojiet viktorīnu