LeetCode刷题实战131:分割回文串
程序IT圈
共 3162字,需浏览 7分钟
·
2020-12-21 15:09
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.
题意
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
解题
public class Solution {
/**
* @param s: A string
* @return: A list of lists of string
*/
List> results;
boolean[][] isPalindrome;
/**
* @param s: A string
* @return: A list of lists of string
*/
public List> partition(String s) {
results = new ArrayList<>();
if (s == null || s.length() == 0) {
return results;
}
getIsPalindrome(s);
helper(s, 0, new ArrayList());
return results;
}
private void getIsPalindrome(String s) {
int n = s.length();
isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < n - 1; i++) {
isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
for (int i = n - 3; i >= 0; i--) {
for (int j = i + 2; j < n; j++) {
isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
}
}
}
private void helper(String s,
int startIndex,
Listpartition ) {
if (startIndex == s.length()) {
addResult(s, partition);
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (!isPalindrome[startIndex][i]) {
continue;
}
partition.add(i);
helper(s, i + 1, partition);
partition.remove(partition.size() - 1);
}
}
private void addResult(String s, Listpartition ) {
Listresult = new ArrayList<>();
int startIndex = 0;
for (int i = 0; i < partition.size(); i++) {
result.add(s.substring(startIndex, partition.get(i) + 1));
startIndex = partition.get(i) + 1;
}
results.add(result);
}
}
评论