Java Simple Recursion


  • 0
    public class Solution {
        private List<List<String>> res;
        private int[][] palindromeMap;
        
        public List<List<String>> partition(String s) {
            res = new ArrayList<List<String>>();
            if(s == null) return res;
            char[] cs = s.toCharArray();
            int len = cs.length;
            palindromeMap = new int[len][len];
            LinkedList<String> temp = new LinkedList<String>();
            findPalindrome(cs, temp, 0, len);
            return res;
        }
        
        private void findPalindrome(char[] cs, LinkedList<String> temp, int begin, int len){
            if(begin >= len){
                List<String> newList = new ArrayList<String>();
                for(String s : temp){
                    newList.add(s);
                }
                res.add(newList);
                return;
            }
            int i = 0;
            while(begin+i < len){
                if(palindromeMap[begin][begin+i] == 0){
                    palindromeMap[begin][begin+i] = isPalindrome(cs, begin, begin+i) ? 1 : -1;
                } 
                if(palindromeMap[begin][begin+i] == 1){
                    StringBuilder sb = new StringBuilder();
                    for(int j = begin; j <= begin+i; ++j){
                        sb.append(cs[j]);
                    }
                    temp.add(sb.toString());
                    findPalindrome(cs, temp, begin+i+1, len);
                    temp.removeLast();
                }
                ++i;
            }
        }
        
        private boolean isPalindrome(char[] cs, int begin, int end){
            while(begin <= end){
                if(cs[begin] != cs[end]) return false;
                ++begin;
                --end;
            }
            return true;
        }
    }
    

Log in to reply
 

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