Much better understandable Java Backtracking solution.


  • 0
    W

    Just treated it as a frog jump problem. Check whether the content that the frog jump through is a palindrome. And take any steps less than the steps left.

    '''

    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s.length() == 0) {
            return res;
        }
        helperPartition(res, new ArrayList<>(), 0, s);
        return res;
    }
    
    
    public void helperPartition(List<List<String>> res, List<String> tempList, int stepMade, String s) {
        if (stepMade == s.length()) {
            res.add(new ArrayList(tempList));
        } else {
            for (int i = 1; i <= (s.length() - stepMade); i++) {
                String temp = s.substring(stepMade, stepMade + i);
                if (!isPalindrome(temp)) continue;
                tempList.add(temp);
                helperPartition(res, tempList, stepMade + i, s);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
    
    public boolean isPalindrome(String s){
        int left = 0, right = s.length() - 1;
        
        while (left < right){
            if (s.charAt(left++) != s.charAt(right--))
                return false;
        }
        
        return true;
    }
    

    '''


Log in to reply
 

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