資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時裝研究
法律研究迴文分割
在此演算法中，輸入是一個字串，將此字串進行分割就是迴文分割，分割後的每個子字串都必須是迴文字串。
在此演算法中，我們必須找到將給定字串進行迴文分割所需的最小切割次數。
輸入與輸出
Input: A string. Say “ababbbabbababa” Output: Minimum cut to partition as palindrome. Here 3 cuts are needed. The palindromes are: a | babbbab | b | ababa
演算法
minPalPart(str)
輸入：給定的字串。
輸出：從字串進行迴文分割所需的最小次數。
Begin n := length of str define cut matrix and pal matrix each of order n x n for i := 0 to n, do pal[i, i] := true cut[i, i] := 0 done for len in range 2 to n, do for i in range 0 to n – len, do j := i + len – 1 if len = 2, then if str[i] = str[j] pal[i, j] := true else if str[i] = str[j] and pal[i+1, j-1] ≠ 0 pal[i, j] := true if pal[i, j] is true, then cut[i, j] := 0 else cut[i, j] := ∞ for k in range i to j-1, do cut[i, j] := minimum of cut[i, j] and (cut[i, k]+ cut[k+1, j+1]+1) done done done return cut[0, n-1] End
示例
#include <iostream>
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 jth 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);
}輸出
Min cuts for Palindrome Partitioning is: 3
更新於：2020-6-17
333 次瀏覽
廣告