資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的有效迴文 III
假設我們有一個字串 s 和另一個數字 k；我們需要檢查給定的字串是否為 K-迴文。
如果一個字串可以透過最多刪除 k 個字元而變成迴文，則稱該字串為 K-迴文。
因此，如果輸入類似於 s = "abcdeca"，k = 2，則輸出將為真，因為透過刪除 'b' 和 'e' 字元，它將成為迴文。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 lcs()，它將接收 s、t，
n := s 的大小
在 s 之前新增一個空格
在 t 之前新增一個空格
定義一個大小為 (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] 與 t[j] 相同，則：
dp[i, j] := dp[i, j] 和 1 + dp[i - 1, j - 1] 的最大值
返回 dp[n, n]
從主方法執行以下操作：
如果 s 的大小不為 0，則：
返回 true
x := 空格
初始化 i := s 的大小，當 i >= 0 時，更新（i 減 1），執行：
x := x + s[i]
返回 s 的大小
讓我們檢視以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lcs(string s, string t){
int n = s.size();
s = " " + s;
t = " " + t;
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] == t[j])
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
return dp[n][n];
}
bool isValidPalindrome(string s, int k) {
if (!s.size())
return true;
string x = "";
for (int i = s.size() - 1; i >= 0; i--)
x += s[i];
return s.size() - lcs(s, x) <= k;
}
};
main(){
Solution ob;
cout << (ob.isValidPalindrome("abcdeca", 2));
}輸入
"abcdeca", 2
輸出
1
更新於: 2020-07-11
379 次檢視
廣告