資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將字串轉換為迴文串的最小插入步驟
假設我們有一個字串 s，我們需要將其轉換為迴文串。在每一步中，我們可以在任何位置插入任何字元，我們需要找到使字串成為迴文串所需的最小字元數。如果字串是“mad”，則答案將是 2，因為我們可以新增“da”到“mad”之前，或“am”到“mad”之後以使其成為迴文串。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 lcs()，它將接收 s，x := s
- n := s 的大小
- 反轉字串 x
- s := 在 s 前面連線空格，x := 在 x 前面連線空格
- 定義一個大小為 (n + 1) x (n + 1) 的二維陣列 dp
- 初始化 i := 1，當 i <= n 時，更新（i 增加 1），執行：
- 初始化 j := 1，當 j <= n 時，更新（j 增加 1），執行：
- dp[i, j] := dp[i – 1, j] 和 dp[i, j - 1] 的最大值
- 如果 s[i] 與 x[j] 相同，則：
- dp[i, j] := dp[i, j] 和 dp[i – 1, j - 1] + 1 的最大值
- 初始化 j := 1，當 j <= n 時，更新（j 增加 1），執行：
- 返回 dp[n, n]
- 從主方法返回 s 的大小 - lcs(s)
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lcs(string s){
string x = s;
int n = s.size();
reverse(x.begin(), x.end());
s = " " + s;
x = " " + x;
vector < vector <int> > dp(n + 1, vector <int>(n + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if(s[i] == x[j]){
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[n][n];
}
int minInsertions(string s) {
return s.size() - lcs(s);
}
};
main(){
Solution ob;
cout << (ob.minInsertions("mad"));
}輸入
“mad”
輸出
2
更新於: 2020-06-02
228 次檢視
廣告