Palindrome Partitioning II--LeetCode

冷不防 2022-08-07 12:56 32阅读 0赞

# 题目： #

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = `"aab"`,  
Return `1` since the palindrome partitioning `["aa","b"]` could be produced using 1 cut.

思路：和上面一题一样，找出所有的可能，从中找出分割次数最少的。

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    bool check(string& str,int begin,int end)
    {
         int i = begin ;
         int j = end;
         for(;i<=j;i++,j--)
          if(str[i] != str[j])
            return false;
          return true;
    }
    
    void helper(string& str,int begin,int end,vector<int>& pos,int& count)
    {
        int i,j,k;
        if(begin > end)
        {
            int k =0;
            for(j=0;j<pos.size();j++)
            {
               if(pos[j] != -1 && j != pos.size()-1)
               {
                k++;
                pos[j] = -1; 
               }
               /*
               cout<<str[j];
               if(pos[j] != -1)
               {
                 cout<<",";
                 pos[j] = -1;
               } */                       
            }   
             if(k < count)
             count = k; 
           // cout<<endl;     
        }
        for(i= begin;i<=end;i++)
        {
            if(check(str,begin,i))
            {
                pos[i] = i-begin+1;
                helper(str,i+1,end,pos,count);  
            }  
        }     
    }
    
    int PalindromePartition(string& str)
    {
         if(str.length() == 0)
          return 0;
         vector<int> pos(str.length(),-1);
         int count=str.length()-1;
         helper(str,0,str.length()-1,pos,count);
         return count;
    }
    
    int main()
    {
        string str("aab");
        cout<<PalindromePartition(str);
        system("pause");
        return 0;
    }

其实这个题目比上一个题目更加简单，因为之间看分割的最少次数，同样的分割方式，只不过需要关注的是分割的最少次数