Easy to understand Java solution using backtracking

  • 0
    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));
            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;
                helper(index+len, s, result, list);
        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.