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. http://leetcode.com/onlinejudge#question_132

PalidromeParts.cs

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Console.WriteLine(CutPalidrome("bananadad"));
    }
    static int CutPalidrome(string s)
    {
        //assume everything from end is palidrome
        //recurse until the string is emppy
        int n = s.Length;
        List<string> palidromeCuts = new List<string>(n);
        int i = 0;
        string ss = string.Empty;
        while(i < n)
        {
            for (int j = n; j > i; j--)
            {
                ss = s.Substring(i,j-i);
                if (IsPalindrome(ss))
                {
                    palidromeCuts.Add(ss);
                    i = j;
                    break;
                }
            }
        }
        return palidromeCuts.Count-1;
    }

    static bool IsPalindrome(string word)
    {
        int n = word.Length;
        if (n == 1)
            return true;
        int i = 0;
        int j = n-1;
        while (i < j)
        {
            if (word[i] != word[j])
                return false;
            i++;
            j--;
        }
        return true;
    }
}