Java Simple Backtracking Solution


  • 1
    X
    class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList();
            List<String> cur = new ArrayList();
            helper(res, cur, s, 0);
            return res;
        }
        
        public void helper(List<List<String>> res, List<String> cur, String s, int begin) {
            if (begin == s.length()) {
                List<String> temp = new ArrayList(cur);
                res.add(temp);
                return;
            }
            for (int i = begin; i < s.length(); i++) {
                if (isPalindrome(s.substring(begin, i + 1))) {
                    cur.add(s.substring(begin, i + 1));
                    helper(res, cur, s, i + 1);
                    cur.remove(cur.size() - 1);
                }
            }
        }
        
        public boolean isPalindrome (String s) {
            if (s == null || s.length() < 2) return true;
            int begin = 0;
            int end = s.length() - 1;
            while (begin < end) {
                if (s.charAt(begin) != s.charAt(end)) return false;
                begin++;
                end--;
            }
            return true;
        }
    }
    

  • 0
    S

Log in to reply
 

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