131 Palindrome Partitioning

131. Palindrome Partitioning​
1. Question
Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return all possible palindrome partitioning ofs.
For example, givens="aab",
Return
1
[
2
  ["aa","b"],
3
  ["a","a","b"]
4
]
Copied!
2. Implementation
(1) Backtracking
1
class Solution {
2
    public List<List<String>> partition(String s) {
3
        List<List<String>> res = new ArrayList<>();
4
        List<String> palindromes = new ArrayList<>();
5
        getPartitions(0, s, palindromes, res);
6
        return res;
7
    }
8
​
9
    public void getPartitions(int index, String s, List<String> palindromes, List<List<String>> res) {
10
        if (index == s.length()) {
11
            res.add(new ArrayList<>(palindromes));
12
            return;
13
        }
14
​
15
        for (int i = index; i < s.length(); i++) {
16
            if (isPalindrome(s, index, i)) {
17
                palindromes.add(s.substring(index, i + 1));
18
                getPartitions(i + 1, s, palindromes, res);
19
                palindromes.remove(palindromes.size() - 1);
20
            }
21
        }
22
    }
23
​
24
    public boolean isPalindrome(String s, int start, int end) {
25
        while (start < end) {
26
            if (s.charAt(start) != s.charAt(end)) {
27
                return false;
28
            }
29
            ++start;
30
            --end;
31
        }
32
        return true;
33
    }
34
}
Copied!
3. Time & Space Complexity
Backtracking: 时间复杂度O(n * 2^n), 空间复杂度O(2^n)

93 Restore IP Addresses

212 Word Search II

Last modified 2yr ago

Copy link

Contents

131. Palindrome Partitioning

1. Question

2. Implementation

3. Time & Space Complexity

131. Palindrome Partitioning​

1. Question

2. Implementation

3. Time & Space Complexity

131. Palindrome Partitioning