C ++中的回文分割

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个输入字符串，那么当该分区的每个子字符串都是回文时，该字符串的分区就是回文分区。在本节中，我们必须找到回文分割给定字符串所需的最小切割数。因此，如果字符串像“ ababbbabbababa”，则最小分割为回文。这里需要3个切口。回文是：babbbab | b | 阿巴巴

为了解决这个问题，我们将遵循以下步骤-

  • n：=长度

  • 分别定义nxn阶的cut矩阵和pal矩阵

  • 对于i：= 0至n

    • pal [i，i]：= true和cut [i，i]：= 0

  • 对于2到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]为true，则cut [i，j]：= 0

    • 其他

    • cut [i，j]：= cut [i，j]和（cut [i，k] + cut [k + 1，j + 1] +1）的最小值

    • cut [i，j]：=∞

    • 对于范围i至j-1的k

    • 对于介于0到n – len之间的i，执行

    • 返回割[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

    以上是 C ++中的回文分割 的全部内容， 来源链接： utcz.com/z/321995.html

    回到顶部