資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的迴文分割槽
假設我們有一個輸入字串，將該字串進行分割槽為迴文分割槽，其中分割槽的每一個子串都是迴文。在本節中，我們必須找出對給定字串進行迴文分割槽所需的最小切割次數。因此，如果字串類似於“ababbbabbababa”，則進行迴文分割槽所需的最小切割次數為 3 次。迴文有：a | babbbab | b | ababa
為了解決這個問題，我們將遵循以下這些步驟 −
- n := 字串長度
- 定義一個切割矩陣和一個迴文矩陣，每個矩陣的順序都是 n x n
- 對於 i := 0 到 n 執行以下操作：
- pal[i, i] := true and cut[i, i] := 0
- 對於 len 在範圍 2 到 n 執行以下操作：
- 對於 i 在範圍 0 到 n - len 執行以下操作：
- j := i + len – 1
- 如果 len = 2，則：
- 如果 str[i] = str[j]，則 pal[i, j] := true
- 否則，當 str[i] = str[j] 且 pal[i+1, j-1] ≠ 0 時，pal[i, j] := true
- 如果 pal[i, j] 為真，則 cut[i, j] := 0
- 否則
- cut[i, j] := ∞
- 對於 k 在範圍 i 到 j-1 執行以下操作：
- cut[i, j] := cut[i, j] 與 (cut[i, k]+ cut[k+1, j+1]+1) 的最小值
- 對於 i 在範圍 0 到 n - len 執行以下操作：
- 返回 cut[0, n-1]
示例
讓我們檢視以下實現，以便更好地理解 −
#include <iostream>
#include <climits>
using namespace std;
int min (int a, int b){
return (a < b)? a : b;
}
int minPalPartion(string str){
int n = str.size();
int cut[n][n];
bool pal[n][n]; //true when palindrome present for i to j th element
for (int i=0; i<n; i++){
pal[i][i] = true; //substring of length 1 is plaindrome
cut[i][i] = 0;
}
for (int len=2; len<=n; len++){
for (int i=0; i<n-len+1; i++){//find all substrings of length len
int j = i+len-1; // Set ending index
if (len == 2) //for two character string
pal[i][j] = (str[i] == str[j]);
else //for string of more than two characters
pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];
if (pal[i][j] == true)
cut[i][j] = 0;
else{
cut[i][j] = INT_MAX; //initially set as infinity
for (int k=i; k<=j-1; k++)
cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j]+1);
}
}
}
return cut[0][n-1];
}
int main(){
string str= "ababbbabbababa";
cout << "Min cuts for Palindrome Partitioning is: "<<minPalPartion(str);
}輸入
ababbbabbababa
輸出
Min cuts for Palindrome Partitioning is: 3
更新時間： 2020 年 4 月 28 日
354 次瀏覽
廣告