7ms Concise and easy to understand Java solution (beats 90%)


  • 0
    Z
    public class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<>();
            if (s == null || s.length() == 0) return res;
            
            backtrack(res, new ArrayList<String>(), s, 0);
            return res;
        }
        
        private void backtrack(List<List<String>> res, List<String> tmp, String s, int start) {
            if (start == s.length()) {
                res.add(new ArrayList<String>(tmp));
            } else {
                for (int i = start + 1; i <= s.length(); i++) {
                    if (isPalindrome(s, start, i - 1)) {
                        tmp.add(s.substring(start, i));
                        backtrack(res, tmp, s, i);
                        tmp.remove(tmp.size() - 1);
                    }
                }
            }
        }
        
        private boolean isPalindrome(String s, int i, int j) {
            while (i < j) {
                if (s.charAt(i) == s.charAt(j)) {
                    i++; j--;
                } else return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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