/ Data Structure and Algorithms  

Leetcode 131. Palindrome Partitioning

Question



Give a string, and then cut several times at arbitrary positions to ensure that each substring after cutting is a palindrome string. Output all cutting results that meet the requirements.

Similar Questions

Solution

Break down big problems into small problems, and use the results of small problems to solve current big problems.

For this question, give an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
aabb
First consider cutting at the first position, a | abb
In this way, we only need to know all the results of abb, and then add a to the head of all results
All results of abb are [a b b] [a bb]
Add a to the head of each result, which is [a a b b] [a a bb]

aabb
Consider cutting at the second position again, aa | bb
In this way, we only need to know all the results of bb, and then add aa to the head of all the results
All results of bb are [b b] [bb]
Add aa to the head of each result, which is [aa b b] [aa bb]

aabb
Then consider cutting at the third position, aab | b
Because aab is not a palindrome string, skip directly

aabb
Then consider cutting at the fourth position, aabb |
Because aabb is not a palindrome string, skip directly

In the end all the results are all added up
[a a b b] [a a bb] [aa b b] [aa bb]

The intermediate process to get all the results of abb, aab, etc., and can be done with recursion. In the case of recursive exit point, all substrings of an empty string are just an empty list.

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
39
40
41
42
43
44
45
46
public List<List<String>> partition(String s) {
    return helper(s, 0);
}

private List<List<String>> helper(String s, int start) {
    // exit recursive
    if (start == s.length()) {
        List<List<String>> temp = new ArrayList<>();
        temp.add(new ArrayList<>());

        return temp;
    }

    List<List<String>> result = new ArrayList<>();
    for (int i = start; i < s.length(); i++) {
        // only continue if left part is palindrome
        if (isPalindrome(s.substring(start, i + 1))) {
            String left = s.substring(start, i + 1);

            for (List<String> temp : helper(s, i + 1)) {
                // append left part in beginning
                temp.add(0, left);
                result.add(temp);
            }
        }
    }

    return result;
}

// helper method to check whether a string is palindrome
private boolean isPalindrome(String s) {
    int i = 0;
    int j = s.length() - 1;

    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }

        i++;
        j--;
    }

    return true;
}