131. Palindrome Partitioning

,

DP + Backtracking

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
class Solution {
    public List<List<String>> partition(String s) {
        // 定义 dp[i][j] 表示字符串 s[i, j] 是否为回文字符串，dp[i][j] depends on dp[i + 1][j - 1]
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i + 1 >= j - 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }

        List<List<String>> resultList = new ArrayList<>();
        Deque<String> wordList = new LinkedList<>();
        dfs(resultList, wordList, dp, s, 0);
        return resultList;
    }

    private void dfs(List<List<String>> resultList, Deque<String> wordList, boolean[][] dp, String s, int startIndex) {
        if (startIndex == s.length()) {
            resultList.add(new ArrayList<>(wordList));
            return;
        }

        for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
            if (dp[startIndex][endIndex]) {
                wordList.addLast(s.substring(startIndex, endIndex + 1));
                dfs(resultList, wordList, dp, s, endIndex + 1);
                wordList.removeLast();
            }
        }
    }
}

Backtracking

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
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> resultList = new ArrayList<>();
        List<String> subStrList = new ArrayList<>();
        backtrack(resultList, subStrList, s, 0);
        return resultList;
    }

    private void backtrack(List<List<String>> resultList, List<String> subStrList, String s, int startIndex) {
        if (startIndex == s.length()) {
            resultList.add(new ArrayList<>(subStrList));
            return;
        }

        for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
            // sub str: [startIndex, endIndex]
            if (isPalindrome(s, startIndex, endIndex)) {
                subStrList.add(s.substring(startIndex, endIndex + 1));
                backtrack(resultList, subStrList, s, endIndex + 1);
                subStrList.remove(subStrList.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int startIndex, int endIndex) {
        while (startIndex < endIndex) {
            if (s.charAt(startIndex++) != s.charAt(endIndex--)) {
                return false;
            }
        }
        return true;
    }
}

References

131. Palindrome Partitioning
剑指 Offer II 086. 分割回文子字符串