131. Palindome partitioning

//131. Palindome partitioning

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);

        return result;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
        if(start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for(int end = start + 1; end <= s.length(); end++) {
            String currentSub = s.substring(start, end);
            
            if(isPalindrome(currentSub)) {
                path.add(currentSub);
                backtrack(s, end, path, result);
                path.remove(path.size() - 1);
            }
        }
    }
    
    private boolean isPalindrome(String sub) {
        int left = 0, right = sub.length() - 1;

        while(left < right) {
            if(sub.charAt(left) != sub.charAt(right)) {
                return false;
            }

            left++;
            right--;
        }
        
        return true;
    }
}