LeetCode: 131. Palindrome Partitioning

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

131. Palindrome Partitioning

LeetCode - Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Runtime: 2 ms, faster than 94.23% of Java online submissions for Palindrome Partitioning.
 * Memory Usage: 39.2 MB, less than 95.45% of Java online submissions for Palindrome Partitioning.
 *
 * Copy from: https://leetcode.com/problems/palindrome-partitioning/discuss/41963/Java%3A-Backtracking-solution.[Java: Backtracking solution. - LeetCode Discuss]
 */
public List<List<String>> partition(String s) {
    if (Objects.isNull(s) || s.length() == 0) {
        return Collections.emptyList();
    }
    List<List<String>> result = new LinkedList<>();
    List<String> current = new ArrayList<>();
    dfs(s, 0, current, result);
    return result;
}

private void dfs(String s, int index, List<String> current, List<List<String>> result) {
    if (index == s.length()) {
        result.add(new ArrayList<>(current));
    } else {
        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                current.add(s.substring(index, i + 1));
                dfs(s, i + 1, current, result);
                current.remove(current.size() - 1);
            }
        }
    }
}

private boolean isPalindrome(String s, int low, int high) {
    while (low < high) {
        if (!Objects.equals(s.charAt(low++), s.charAt(high--))) {
            return false;
        }
    }
    return true;
}