資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學最小化移除次數，以將另一個字串作為給定字串的子序列移除
子序列是指可以從另一個序列中移除零個或多個元素而獲得的序列，且不改變剩餘元素的順序。簡單來說，子序列是從原始序列中選擇元素而保留其相對順序匯出的序列。
例如，考慮序列[1, 2, 3, 4]。這個序列的一些可能的子序列是：[1, 2]，[1, 3, 4]，[2, 4]，[1, 2, 3, 4]，[3]和[4]。
問題陳述
目標是確定要從字串s1中移除的最小字元數，以便消除s2作為s1中子序列的任何出現。
例如
Input: s1 = “jjkklll”, s2 = “jkl” Output: 2
解釋
字串s1包含子序列“jkl”。為了使s1不包含s2作為子序列，我們可以從s1中移除兩個'j'或兩個'k'。因此，需要移除的最小字元數為2。
Input: s1 = “”, s2 = “q” Output: 0
解釋
由於s1是一個空字串，因此沒有字元需要移除。因此，不需要移除任何字元，因為需要移除的最小字元數為0。
解決方案方法
為了找到需要從字串s1中移除的最小字元數，以使其不包含字串s2作為子序列，我們可以使用動態規劃方法。其實現如下：
建立一個名為“dp”的二維陣列，其維度為NxM，其中N表示字串s1的長度，M表示字串s2的長度。此陣列將用於儲存需要移除的最小字元數。
透過檢查s2的第一個字元是否與s1的對應字元匹配來填充dp的第一行。如果匹配，則將dp中的值設定為1，表示需要移除一個字元。
從第二行開始迭代dp的行。對於每一行，迭代列。
如果字串s1的當前字元與字串s2的當前字元匹配，我們可以確定需要移除的最小字元數。
計算兩個值的最小值：
從dp陣列的上一行(i - 1)和當前列(j)移除的最小字元數，並加1。
從dp陣列的上一行(i - 1)和上一列(j - 1)移除的最小字元數。
當s1和s2當前位置的字元不匹配時，需要移除的最小字元數與需要從dp陣列的上一行(i - 1)和當前列(j)移除的最小字元數相同。
一旦我們迭代了dp陣列的所有元素，需要移除的最小字元數將儲存在dp[N - 1][M - 1]中，其中N和M分別是字串s1和s2的長度。
最後，我們可以輸出需要從s1中移除的最小字元數，以確保它不包含s2作為子序列。
動態規劃方法透過考慮所有可能的組合並在每一步選擇最少的移除次數來計算最小字元移除數。
演算法
function printMinimumRemovals(s1, s2):
N = length(s1)
M = length(s2)
Create a 2D array dp of size (N) x (M)
// Step 2
For j = 0 to M - 1:
If s1[0] equals s2[j]:
Set dp[0][j] to 1
// Step 3
For i = 1 to N - 1:
For j = 0 to M - 1:
// Step 4
If s1[i] equals s2[j]:
Set dp[i][j] to min(dp[i-1][j] + 1, dp[i-1][j-1])
// Step 5
Else:
Set dp[i][j] to dp[i-1][j]
// Step 6
minimumRemovals = dp[N][M]
// Step 7
print minimumRemovals
function main:
initialise string s1 and s2
function call printMinimumRemovals()
示例：C++程式
給定的程式碼解決了查詢需要從字串s1中移除的最小字元數以使其成為字串s2的子序列的問題。該程式碼使用動態規劃來計算此最小移除計數。
printMinimumRemovals函式以兩個字串s1和s2作為輸入。它建立一個二維陣列dp來儲存所需的最小移除次數。在迭代dp的所有元素之後，最少的字元移除數儲存在dp[N - 1][M - 1]中。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// This function prints the minimum number of characters that need to be removed from the string `s1` to make it a subsequence of the string `s2`.
void printMinimumRemovals(string s1, string s2){
int N = s1.length();
int M = s2.length();
// Create a 2D array to store the minimum number of characters that need to be removed from the first `i` characters of `` to make it a subsequence of the first `j` characters of `s2`.
vector<vector<int>> dp(N, vector<int>(M));
// Fill the first row of the array.
for (int j = 0; j < M; j++){
// If the first character of `s2` matches the first character of `s1`, then the minimum number of characters that need to be removed is 1.
if (s1[0] == s2[j]){
dp[0][j] = 1;
}
}
// Iterate over the rows of the array.
for (int i = 1; i < N; i++){
// Iterate over the columns of the array.
for (int j = 0; j < M; j++){
// When the current character of s1 matches the current character of s2, the minimum number of characters to be removed is determined by taking the smaller value between two scenarios:
// Removing the minimum number of characters needed to make the first i - 1 characters of s1 a subsequence of the first j characters of s2.
// Removing the minimum number of characters needed to make the first i - 1 characters of s1 a subsequence of the first j - 1 characters of s2.
if (s1[i] == s2[j]){
dp[i][j] = min(dp[i - 1][j] + 1, dp[i - 1][j - 1]);
}
// In case of non-matching characters, consider the minimum number of characters to be removed from the first i - 1 characters of s1 to make it a subsequence of the first j characters of s2.
else{
dp[i][j] = dp[i - 1][j];
}
}
}
// Print the minimum number of characters that need to be removed.
cout << dp[N - 1][M - 1] << endl;
}
int main(){
// Input
string s1 = "bb";
string s2 = "b";
// Function call to obtain the minimum number of character removals.
printMinimumRemovals(s1, s2);
return 0;
}
輸出
0
時間和空間複雜度分析
時間複雜度 - O(N*M)
建立大小為NxM的二維向量dp需要O(N*M)的時間。
填充dp的第一行需要O(M)的時間，因為它迭代s2的長度。
迭代dp的行和列的巢狀迴圈總共需要O(N*M)的時間，因為二維陣列的每個元素都被處理一次。
程式碼的時間複雜度主要由巢狀迴圈決定，導致整體時間複雜度為O(N*M)。
空間複雜度 - O(N*M)
程式碼的空間複雜度為O(N + M)，其中N和M分別是字串s1和s2的長度，因為它取決於輸入字串的大小。
建立大小為NxM的二維向量dp需要O(N*M)的空間。
結論
本文討論了針對問題陳述的動態規劃方法。透過合適的示例解釋了問題的概念。解決方案方法包括所涉及的步驟、使用的演算法、C++程式實現以及時間和空間複雜度分析。
瀏覽量：163
