두 개의 문자열이 주어지면 s1 그리고 s2 . 과제는 제거/삭제 그리고 끼워 넣다 그만큼 최소 문자 수 ~에서 s1 그것을로 변환하는 것 s2 . 다음과 같은 일이 일어날 수도 있습니다. 같은 캐릭터 한 지점에서 제거/삭제해야 합니다. s1 그리고 다른 지점에 삽입했습니다.
예시 1:
입력: s1 = '힙' s2 =
산출: 3
설명: 최소 삭제 = 2 및 최소 삽입 = 1
p와 h는 힙에서 삭제된 다음 p가 처음에 삽입됩니다. p가 필요하지만 주의할 점은 먼저 해당 위치에서 제거/삭제된 다음 다른 위치에 삽입되었습니다. 따라서 p는 삭제 횟수에 하나, 삽입 횟수에 하나를 기여합니다.입력: s1 = '긱스포긱스' s2 = '긱스'
산출: 8
설명: 8개 삭제, 즉 'forgeeks' 문자열의 모든 문자를 제거합니다.
목차
- 재귀 사용 - O(2^n) 시간 및 O(n) 공간
- Top-Down DP(Memoization) 사용 - 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
Top-Down DP(Memoization) 사용 - O(n^2) 시간 및 O(n^2) 공간
C++이 접근 방식에서 우리는 적용합니다 메모이제이션 LCS(Longest Common Subsequence)를 찾는 동안 겹치는 하위 문제의 결과를 저장합니다. 에이 2차원 배열 메모 저장하는 데 사용됩니다. 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++접근 방식은 다음과 유사합니다. 이전 것 문제를 분해하는 것보다 재귀적으로 우리 반복적으로 계산하여 솔루션 구축 상향식 방법. 우리는 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퀴즈 만들기