[Leetcode单排] 分割回文串 (N131)

字数统计: 263阅读时长: 1 min

 2019/08/04  Share

131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

DFS 回溯典型问题。基本同 N93 复原IP地址问题。

需要注意的是 handle方法里面 for 的终止条件，一开始写的是i < str.length()，发现最后一个字符总是漏掉，主要是 substring 的第二个参数在截取的时候 exclude，i 这个值本身可以等于 length。

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    if (s == null || s.length() == 0) {
        return result;
    }
    handle(s, 0, new ArrayList<>(), result);
    return result;
}

private void handle(String str, int index, List<String> curList, List<List<String>> result) {
    if (index == str.length()) {
        result.add(new ArrayList<>(curList));
        return;
    }
    for (int i = index + 1; i <= str.length(); i++) {
        if (isPalindrome(str.substring(index, i))) {
            curList.add(str.substring(index, i));
            handle(str, i, curList, result);
            curList.remove(curList.size() - 1);
        }
    }
}

private boolean isPalindrome(String str) {
    if (str == null || str.length() == 0) {
        return false;
    }
    if (str.length() == 1) {
        return true;
    }
    for (int i = 0; i < str.length() / 2; i++) {
        if (str.charAt(i) != str.charAt(str.length() - i - 1)) {
            return false;
        }
    }
    return true;
}

Next Post

[Leetcode单排] 运算表达式设优先级求值 (N241)
Previous Post

[Leetcode单排] 复原IP地址 (N93)

CATALOG

1. 131. Palindrome Partitioning

