資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中使字串變為迴文的最小追加次數
問題陳述
給定一個字串，找出追加到它能使其變為迴文的最小字元數。
示例
如果字串為 abcac，我們可以透過追加 2 個高亮的字元來使其變為迴文，例如 abcacba
演算法
- 檢查字串是否已經是迴文，如果是，則無需追加任何字元。
- 逐個從字串中移除一個字元，並檢查剩下的字串是否是迴文
- 重複上述過程，直到字串變為迴文
- 返回到目前為止移除的字元數作為最終答案
示例
#include <iostream>
#include <cstring>
using namespace std;
bool isPalindrome(char *str) {
int n = strlen(str);
if (n == 1) {
return true;
}
int start = 0, end = n - 1;
while (start < end) {
if (str[start] != str[end]) {
return false;
}
++start;
--end;
}
return true;
}
int requiredAppends(char *str) {
if (isPalindrome(str)) {
return 0;
}
return 1 + requiredAppends(str + 1);
}
int main() {
char *str = "abcac";
cout << "Characters to be appended = " << requiredAppends(str) << endl;
return 0;
}輸出
當您編譯並執行以上的程式時，它會生成以下輸出：
Characters to be appended = 2
更新日期： 2019 年 11 月 22 日
345 次瀏覽
廣告