Recursive approach - Backtracking


  • 0
    S

    Coded in C#.

    Runs in O(n^2) time complexity if we were to consider IsPalindrome(...) to run in O(1)

    public class Solution {
        IList<IList<string>> output  = new List<IList<string>>();
        int e = 0;
        public IList<IList<string>> Partition(string s) {
            e = s.Length - 1;
            Helper(new List<string>(), s, 0);
            return output;
        }
        
        void Helper(List<string> res, string s, int b)
        {
            // terminal condition
            if(b == e)
            {
                res.Add(s.Substring(b, e-b+1));
                output.Add(new List<string>(res));
                res.RemoveAt(res.Count-1);
                return;
            }
            
            // semi-terminal condition
            if(IsPalindrome(s, b, e))
            {
                res.Add(s.Substring(b, e-b+1));
                output.Add(new List<string>(res));
                res.RemoveAt(res.Count-1);
            }
                
            for(int i = 0; i < e - b; i++)
            {
                string sub = s.Substring(b, i+1);
                if(IsPalindrome(s, b, b+i))
                {
                    res.Add(sub);
                    Helper(res, s, b+i+1);
                    res.RemoveAt(res.Count-1);
                }
            }
        }
        
        bool IsPalindrome(string s, int b, int e)
        {
            if(b == e)
                return true;
            while(b < e)
            {
                if(s[b] != s[e])
                    return false;
                b++;
                e--;
            }
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.