Easy to understand Java solution using backtracking


  • 0
    T
    public class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> result = new ArrayList<>();
            if(s == null || s.length()==0) return result;
            
            helper(0, s, result, new ArrayList<String>());
            return result;
        }
        
        private void helper(int index, String s, List<List<String>> result, List<String> list){
    
            if(index >= s.length()){
                //if we have found a solution
                result.add(new ArrayList<String>(list));
                return;
            }
            for(int len = 1;len<=s.length();len++){
                //if the string we are making is out of bounds then return
               // `return` since all further strings will be out of bounds.
    
                if(index+len>s.length()) return;
    
                String curr = s.substring(index, index+len);
                // if the string we created is not palindrome, lets try a bigger length string
               // **NOTE** that we are not returning here as previously because there could be a larger length palindrome here.
    
                if(!isPalindrome(curr)) continue;
                    
                list.add(curr);
                helper(index+len, s, result, list);
                list.remove(list.size()-1);
            }    
        }
        
        private boolean isPalindrome(String s){
            if(s==null || s.isEmpty()) return true;
            int n = s.length();
            for(int i = 0;i<n/2;i++){
                if(s.charAt(i)!=s.charAt(n-1-i)) return false;
            }
            return true;
        }
    }

Log in to reply
 

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