Очень похожие проблемы:родительская логика, которую нужно понять → самая длинная общая подпоследовательность
Самая длинная общая подпоследовательность (LCS)
Самая длинная общая подстрока — используется LCS
Самая длинная палиндромная подпоследовательность — используется LCS
Минимальные шаги вставки для создания строкового палиндрома → используется LCS -> Длина подпоследовательности палиндрома обратно пропорциональна минимальному количеству удалений или вставок.
Операция удаления двух строк → используется LCS → Длина подпоследовательности палиндрома обратно пропорциональна минимальному количеству удалений или вставок.
Кратчайшая общая суперпоследовательность - › использует LCS
Отличные подпоследовательности | Техника оптимизации 1D-массива — аналогична LCS
Редактировать расстояние — аналогично LCS
Самая длинная общая подпоследовательность
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
Самая длинная общая подстрока
Input : X = “GeeksforGeeks”, y = “GeeksQuiz” Output : 5 Explanation: The longest common substring is “Geeks” and is of length 5. Input : X = “abcdxyz”, y = “xyzabcd” Output : 4 Explanation:
Табуляция – сверху вниз
function longestCommonSubstring(X, Y) {
const m = X.length;
const n = Y.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
let maxLength = 0; // To keep track of the maximum length found.
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (X[i - 1] === Y[j - 1]) {
//if characters are matching
dp[i][j] = dp[i - 1][j - 1] + 1;
// caluclate lenth of subString
maxLength = Math.max(maxLength, dp[i][j]);
} else {
dp[i][j] = 0; // If characters don't match, reset the length to 0.
}
}
}
return maxLength;
}
// Test cases
const X1 = "GeeksforGeeks";
const Y1 = "GeeksQuiz";
const result1 = longestCommonSubstring(X1, Y1);
console.log(`The length of the longest common substring is ${result1}.`);
const X2 = "abcdxyz";
const Y2 = "xyzabcd";
const result2 = longestCommonSubstring(X2, Y2);
console.log(`The length of the longest common substring is ${result2}.`);
Самая длинная палиндромная подпоследовательность
Учитывая строку s, найдите длину самой длинной палиндромной подпоследовательности в s.
Подпоследовательность – это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов или их отсутствия без изменения порядка остальных элементов.
Пример 1:
Input: s = "bbbab" Output: 4 Explanation: One possible longest palindromic subsequence is "bbbb". Input: s = "cbbd" Output: 2 Explanation: One possible longest palindromic subsequence is "bb".
Рекурсивный + Мемоизация
Временная сложность: O(n2)
Вспомогательное пространство:O(n2)
let dp;
// Returns the length of the longest palindromic subsequence in seq
function lps(s1, s2, n1, n2) {
if (n1 == 0 || n2 == 0) {
return 0;
}
if (dp[n1][n2] != -1) {
return dp[n1][n2];
}
if (s1[n1 - 1] == s2[n2 - 1]) {
return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
} else {
return dp[n1][n2] = Math.max(lps(s1, s2, n1 - 1, n2),
lps(s1, s2, n1, n2 - 1));
}
}
/* Driver program to test above functions */
let seq = "GEEKSFORGEEKS";
let n = seq.length;
dp = new Array(n + 1);
for (let i = 0; i <= n; i++) {
dp[i] = new Array(n + 1).fill(-1);
}
let s2 = seq;
s2 = s2.split('').reverse().join('');
console.log("The length of the LPS is " + lps(seq, s2, n, n));
Сверху вниз — табуляция — аналогично LCS (получить другую строку, вернув строку)
function longestPalinSubseq(S)
{
let R = S.split('').reverse().join('');
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
// Initialize dp array with zeros
let dp = new Array(S.length + 1).fill(0).map(() => new Array(R.length + 1).fill(0));
// Filling up DP table based on conditions discussed
// in the above approach
for (let i = 1; i <= S.length; i++) {
for (let j = 1; j <= R.length; j++) {
if (S[i - 1] == R[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return dp[S.length][R.length];
}
// Driver code
let s = "GEEKSFORGEEKS";
console.log("The length of the LPS is " + longestPalinSubseq(s));
Минимальные шаги вставки для создания строкового палиндрома
Верните минимальное количество шагов, чтобы получился палиндром s.
Строка-палиндром — это строка, которая читается одинаково как в прямом, так и в обратном направлении.
Пример 1:
Input: s = "zzazz" Output: 0 Explanation: The string "zzazz" is already palindrome we do not need any insertions.
ПРИМЕЧАНИЕ. Длина самой длинной подпоследовательности палиндрома обратно пропорциональна минимальному количеству удалений или вставок.
Количество вставок = Длина строки — длина LPS
LCS или LPS — для получения счетчика используется Math.MAX.
Минимальная вставка/удаление — для получения счетчика используется Math.min.
Точное решение минимальной вставки/удаления → Самая длинная палиндромная подпоследовательность → Самая длинная общая подпоследовательность
Рекурсивный + мемоизация (строка не перевернута)
- Временная сложность: O(n²)
- Пространственная сложность: O(n²)
function minInsertionsToMakePalindrome(s) {
const n = s.length;
const memo = new Array(n).fill(undefined).map(() => new Array(n).fill(undefined));
function recursiveMinInsertions(i, j) {
if (i >= j) {
return 0;
}
if (memo[i][j] !== undefined) {
return memo[i][j];
}
if (s[i] === s[j]) {
memo[i][j] = recursiveMinInsertions(i + 1, j - 1);
} else {
memo[i][j] = 1 + Math.min(recursiveMinInsertions(i + 1, j), recursiveMinInsertions(i, j - 1));
}
return memo[i][j];
}
return recursiveMinInsertions(0, n - 1);
}
const inputString = "abcdc";
const result = minInsertionsToMakePalindrome(inputString);
console.log(`Minimum insertions required to make "${inputString}" a palindrome: ${result}`);
OR
function minDeletionsToMakePalindrome(s, start, end, memo) {
if (start >= end) {
return 0;
}
if (memo[start][end] !== undefined) {
return memo[start][end];
}
if (s[start] === s[end]) {
memo[start][end] = minDeletionsToMakePalindrome(s, start + 1, end - 1, memo);
} else {
memo[start][end] = 1 + Math.min(
minDeletionsToMakePalindrome(s, start + 1, end, memo),
minDeletionsToMakePalindrome(s, start, end - 1, memo)
);
}
return memo[start][end];
}
function minimumDeletionsToMakePalindrome(s) {
const n = s.length;
const memo = new Array(n).fill(undefined).map(() => new Array(n).fill(undefined));
return minDeletionsToMakePalindrome(s, 0, n - 1, memo);
}
const inputString = "abcdc";
const result = minimumDeletionsToMakePalindrome(inputString);
console.log(`Minimum deletions required to make "${inputString}" a palindrome: ${result}`);
Табуляция — подход «сверху вниз»,
- Временная сложность: O(n²)
- Пространственная сложность: O(n²)
function minInsertionsToMakePalindrome(s) {
const n = s.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
// Initialize the dp table for substrings of length 1 (single characters).
for (let i = 0; i < n; i++) {
dp[i][i] = 0;
}
for (let cl = 2; cl <= n; cl++) {
for (let i = 0; i < n - cl + 1; i++) {
const j = i + cl - 1;
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
const inputString = "abcdc";
const result = minInsertionsToMakePalindrome(inputString);
console.log(`Minimum insertions required to make "${inputString}" a palindrome: ${result}`);
Кратчайшая общая суперпоследовательность
- Общие символы должны принимать один раз → что означает поиск самой длинной общей последовательности.
- Возврат (длина str1 + длина str2 — LCS)
Input --> X = "AGGTAB" and Y = "GXTXAYB." LCS Table -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 -1 0 1 1 1 1 1 1 -1 0 1 1 1 2 2 2 -1 0 1 2 2 2 2 2 -1 0 1 2 2 2 3 3 LCS output - 3 Length of SCS = 6 + 7 - 3 = 10
Рекурсивный + Мемоизация,
function shortestCommonSupersequence(X, Y) {
function lcs(X, Y, m, n, memo) {
if (m === 0 || n === 0) {
return 0;
}
if (memo[m][n] !== -1) {
return memo[m][n];
}
if (X[m - 1] === Y[n - 1]) {
memo[m][n] = 1 + lcs(X, Y, m - 1, n - 1, memo);
} else {
memo[m][n] = Math.max(lcs(X, Y, m - 1, n, memo), lcs(X, Y, m, n - 1, memo));
}
return memo[m][n];
}
const m = X.length;
const n = Y.length;
const memo = new Array(m + 1).fill(undefined).map(() => new Array(n + 1).fill(-1));
const lcs_length = lcs(X, Y, m, n, memo);
return m + n - lcs_length;
}
// Example usage:
const X = "AGGTAB";
const Y = "GXTXAYB";
const result = shortestCommonSupersequence(X, Y);
console.log(`The length of the shortest common supersequence is: ${result}`);
Табуляция,
function shortestSuperSequence(X, Y)
{
var m = X.length;
var n = Y.length;
// find lcs
var l = lcs(X, Y, m, n);
// Result is sum of input string
// lengths - length of lcs
return (m + n - l);
}
// Returns length of LCS
// for X[0..m - 1], Y[0..n - 1]
function lcs(X, Y , m , n)
{
var L = Array(m+1).fill(0).map(x => Array(n+1).fill(0));
var i, j;
// Following steps build L[m + 1][n + 1]
// in bottom up fashion. Note that
// L[i][j] contains length of LCS
// of X[0..i - 1]and Y[0..j - 1]
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X.charAt(i - 1) == Y.charAt(j - 1))
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = Math.max(L[i - 1][j],
L[i][j - 1]);
}
}
// L[m][n] contains length of LCS
// for X[0..n - 1] and Y[0..m - 1]
return L[m][n];
}
Отличные подпоследовательности — 1D
function numDistinct(S, T) {
// Helper function to count distinct subsequences starting from indices sIndex and tIndex.
function countDistinctSubsequences(sIndex, tIndex) {
// If we have matched all characters in T, we found a valid subsequence.
if (tIndex === T.length) {
return 1;
}
// If we have reached the end of S but not T, there are no valid subsequences.
if (sIndex === S.length) {
return 0;
}
// Initialize the count to consider the current character in S.
let count = 0;
// If the current characters in S and T match, we have two choices:
// 1. Include the current character from S in the subsequence.
// 2. Skip the current character from S and continue with the next character in S.
if (S[sIndex] === T[tIndex]) {
count += countDistinctSubsequences(sIndex + 1, tIndex + 1) +
countDistinctSubsequences(sIndex + 1, tIndex);
} else {
// If the characters do not match, we can only skip the current character in S.
count += countDistinctSubsequences(sIndex + 1, tIndex);
}
return count;
}
// Start the recursion from the beginning of both strings.
return countDistinctSubsequences(0, 0);
}
// Example usage:
const S = "rabbbit";
const T = "rabbit";
const result = numDistinct(S, T);
console.log(`The number of distinct subsequences is: ${result}`);
Табуляция,
function numDistinct(str1, str2) {
const m = str1.length;
const n = str2.length;
// Create a 2D DP table with dimensions (m+1) x (n+1) and initialize it with 0s.
const dp = new Array(m + 1).fill(undefined).map(() => new Array(n + 1).fill(0));
// Base case: There's one way to form an empty subsequence from any string.
for (let i = 0; i <= m; i++) {
dp[i][0] = 1;
}
// Fill in the DP table using a bottom-up approach.
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (str1[i - 1] === str2[j - 1]) {
// If the characters match, we can either include
// the current character from str1 or skip it.
// Add the two possibilities.
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
// If the characters do not match,
// we can only skip the current character in str1.
dp[i][j] = dp[i - 1][j];
}
}
}
// The final value in the DP table represents the number of distinct subsequences.
return dp[m][n];
}
// Example usage:
const str1 = "rabbbit";
const str2 = "rabbit";
const result = numDistinct(str1, str2);
console.log(`The number of distinct subsequences is: ${result}`);
Редактировать расстояние
Учитывая две строки word1 и word2, верните минимальное количество операций, необходимое для преобразования word1 в word2.
Над словом разрешены следующие три операции:
- Вставить символ → (i, j-1)
- Удалить символ (i-1, j)
- Заменить символ (i-1, j-1)
Рекурсивный,
function minDistance(word1, word2) {
function minOperations(i, j) {
// If either string is empty, we need to perform insert/delete operations
if (i === 0) {
return j;
}
if (j === 0) {
return i;
}
// If the current characters match, no additional operation is needed
if (word1[i - 1] === word2[j - 1]) {
return minOperations(i - 1, j - 1);
}
// Calculate the minimum of three possible operations: insert, delete, or replace
return 1 + Math.min(
minOperations(i, j - 1), // Insert operation
minOperations(i - 1, j), // Delete operation
minOperations(i - 1, j - 1) // Replace operation
);
}
// Start the recursion with the lengths of both words
return minOperations(word1.length, word2.length);
}
// Example usage:
const word1 = "horse";
const word2 = "ros";
const result = minDistance(word1, word2);
console.log(`The minimum number of operations is: ${result}`);
Мемоизация
function minDistance(word1, word2) {
// Define a memoization table to store already computed values
const memo = [];
function minOperations(i, j) {
// Check if the result is already computed and stored in the memo table
if (memo[i] !== undefined && memo[i][j] !== undefined) {
return memo[i][j];
}
// If either string is empty, we need to perform insert/delete operations
if (i === 0) {
memo[i] = memo[i] || [];
memo[i][j] = j;
} else if (j === 0) {
memo[i] = memo[i] || [];
memo[i][j] = i;
} else {
// If the current characters match, no additional operation is needed
if (word1[i - 1] === word2[j - 1]) {
memo[i] = memo[i] || [];
memo[i][j] = minOperations(i - 1, j - 1);
} else {
// Calculate the minimum of three possible operations: insert, delete, or replace
memo[i] = memo[i] || [];
memo[i][j] = 1 + Math.min(
minOperations(i, j - 1), // Insert operation
minOperations(i - 1, j), // Delete operation
minOperations(i - 1, j - 1) // Replace operation
);
}
}
return memo[i][j];
}
// Start the recursion with the lengths of both words
return minOperations(word1.length, word2.length);
}
- 👏 Пожалуйста, аплодируйте этой истории и подписывайтесь на меня 👉
- 📰 Посмотреть больше контента по теме Javascript, DSA, React, Подготовка к собеседованию
- 🔔 Следуйте за мной: LinkedIn!
Я знаю, что всегда можно что-то улучшить. Пожалуйста, не стесняйтесь поделиться своими мыслями
Самая длинная общая подпоследовательность
Самая длинная общая подстрока
Самая длинная палиндромная подпоследовательность
Минимальные шаги вставки для создания строкового палиндрома
Операция удаления для двух строк
Кратчайшая общая суперпоследовательность
Различные подпоследовательности | Техника оптимизации одномерного массива — аналогична LCS
Редактировать расстояние — аналогично LCS
Сопоставление регулярных выражений — аналогично LCS
