資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：計算字串在最小分割次數後的迴文數量
假設我們有一個小寫字串s，我們必須將其分割成儘可能少的字串，使得每個字串都是迴文，然後找到字串的數量。
因此，如果輸入類似於s = "levelracecar"，則輸出將為2，因為有兩個迴文"level"和"racecar"。
為了解決這個問題，我們將遵循以下步驟：
n := A的長度
定義一個大小為(n + 1)的陣列result
result[n] := -1
for i := n - 1 to 0 (遞減):
result[i] := n - i - 1
for j := i to n (遞增):
如果A從i到j - i的子串是迴文，則：
result[i] := min(result[i], 1 + result[j + 1])
return result[0] + 1
示例
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPalindrome(string A) {
int left = 0;
int right = A.size() - 1;
while (left < right) {
if (A[left] != A[right]) {
return 0;
}
left++;
right--;
}
return 1;
}
int solve(string A) {
int n = A.size();
vector<int> result(n + 1);
result[n] = -1;
for (int i = n - 1; i >= 0; i--) {
result[i] = n - i - 1;
for (int j = i; j < n; j++) {
if (isPalindrome(A.substr(i, j - i + 1))) {
result[i] = min(result[i], 1 + result[j + 1]);
}
}
}
return result[0] + 1;
}
};
int solve(string s) {
return (new Solution())->solve(s);
}
int main(){
string s = "levelracecar";
cout << solve(s);
}輸入
"levelracecar"
輸出
2
更新於：2020年12月23日
116次瀏覽
廣告