My DP solution implemented in Java


  • 0

    /*here I use a 2d array(memTable), so we do not need to call isPalindrome() to check if currently substring is valid palindrome or not. */

     public class Solution {
        public List<List<String>> partition(String s) {
            int len = s.length();
            if(len<=0||s == null)
            {
                 return new ArrayList<List<String>>();
            }
               
            List<List<String>>retList = new ArrayList<List<String>>();
            ArrayList<String> curLine = new ArrayList<String>();
            int[][] memTable = new int[len][len];
            recur(retList, 0, s, curLine, memTable);
            return retList;
        
        }
        public void recur(List<List<String>> retList, int start, String str, ArrayList<String> curLine, int[][] memTable)
        {
            
            int len = str.length();
           
            if(start == len) 
            {
                retList.add(new ArrayList<String>(curLine));
                return;
            }
            for(int i = start; i<len;i++)
            {
                switch(memTable[start][i])
                {
                    case 0:  //int[][] default value
                        if(isPalindrome(str.substring(start, i+1))) // substring is [ )
                        {
                            memTable[start][i] = 1;
                        }
                        else
                        {
                            memTable[start][i] = -1;
                            break;
                        }
                     case 1: //if previously accessed and is valid palindrome  
                        curLine.add(str.substring(start, i+1));
                        recur(retList, i+1, str, curLine, memTable);
                        curLine.remove(curLine.size()-1);
                        break;
                    case -1: //if previously accessed and is invalid palindrome  
                        break;
                }
            }
             
        }
        
        public boolean isPalindrome(String str)
        {
            int len = str.length();
            if(len == 1) return true;
            int left = 0;
            int right =len-1;
            while(left<right)
            {
                if(str.charAt(left)!=str.charAt(right))
                    {return false;}
                else
                {
                    left++;
                    right--;
                }
            }
            return true;
        }
    }

Log in to reply
 

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