转载

palindrome-partition-ii

palindrome-partition-ii

题目描述

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”,
Return1since the palindrome partitioning[“aa”,”b”]could be produced using 1 cut.

思路

动态规划对这道题太适合不过

代码

#include<iostream>
using namespace std;

class Solution {
public:
    int minCut(string s) {
        if(s.size() == 0) return 0;
        map<int, int> M;

        for(int i = 0; i < s.size(); i++){
            for(int j = 0; j <= i; j++) {
                if(j == i && palindrome(s.substr(0, i + 1))) {
                    M[i] = 0;
                } else {
                    if(M[j] != -1 && palindrome(s.substr(j+1, i-j))) {
                        if(M.count(i) <= 0) M[i] = M[j] + 1;
                        if(M.count(i) > 0 && M[j] + 1 < M[i])
                            M[i] = M[j] + 1;
                    }
                }
            }
            if(M.count(i) <= 0) M[i] = -1;
        }
        return M[s.size()-1];
    }
    bool palindrome(string s){
       int len = s.size();
       for(int i = 0; i < len / 2; i++) {
           if(s[i] != s[len - i -1]) return false;
       }
       return true;
    }
};
正文到此结束
本文目录