Java backtracking 10ms


  • 0
    M
    public List<List<String>> partition(String s) {
        List<List<String>> answer = new ArrayList<List<String>>();
        if (s == null || s.length() == 0) {
            return answer;
        }
        List<String> list = new ArrayList<String>();
        partitionHelper(s, answer, list, 0);
        return answer;
    }
    
    private void partitionHelper(String s, List<List<String>> answer, List<String> list, int index) {
        if (index == s.length()) {
            answer.add(new ArrayList<String>(list));
            return;
        }
        
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if (isPalindrome(str)) {
                list.add(str);
                partitionHelper(s, answer, list, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
    
    private boolean isPalindrome(String str) {
        int start = 0;
        int end = str.length() - 1;
        while (start < end) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

Log in to reply
 

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