Skip to content

Instantly share code, notes, and snippets.

@adamkorg
Created November 4, 2019 12:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save adamkorg/d743bd068ed0bdcff060d25e5f905ec0 to your computer and use it in GitHub Desktop.
Save adamkorg/d743bd068ed0bdcff060d25e5f905ec0 to your computer and use it in GitHub Desktop.
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