Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 132: Palindrome Partitioning II (recursive)
#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(const string& s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) return false;
}
return true;
}
int getMinCuts(const string& s, int start, int end) {
if (end-start == 0 || isPalindrome(s, start, end)) return 0;
int minCuts = INT_MAX;
for (int i=start+1; i<=end; ++i) {
int cuts = 1 + getMinCuts(s, start, i-1) + getMinCuts(s, i, end);
if (cuts < minCuts) minCuts = cuts;
}
return minCuts;
}
int minCut(string s) {
return getMinCuts(s, 0, s.size()-1);
}
int main() {
string s = "eegiicgaeadbcfacfhifdbiehbgejcaeggcgbahfcajfhjjdgj"; //"abcd";
cout << minCut(s) << "\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.