資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究迴文劃分 II（C++）
假設我們有一個字串 s，我們必須找出將這個字串分割成多個子字串並使每部分都成為迴文的所需的切割次數。因此，如果字串類似於“ababba”，那麼這將需要兩次切割。[aba|bb|a]
要解決這個問題，我們將遵循以下步驟 −
n := 字串 s 中的字元數
建立一個稱為 res 的陣列，大小為 n + 1
res[n] := -1
對於 n – 1 到 0 範圍內的 i
res[i] := n – i – 1
對於 i 到 n 範圍內的 j
如果從索引 i 到 j – i 的子字串 a 是迴文，則
res[i] := res[i] 和 1 + res[j + 1] 中的最小值
返回 res[0]
舉例
讓我們看看以下實現，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
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];
}
class Solution {
public:
int minCut(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.minCut("ababba"));
}輸入
“ababba”
輸出
2
更新時間：2020-05-26
122 次瀏覽
廣告