20210307 131. 分割回文串

题目

https://leetcode-cn.com/problems/palindrome-partitioning/

题解

递归调用,dfs(String s, int startIndex, int endIndex, Stack<String> path, List<List<String>> result) path存储已经分割过的路径,result存储结果,startIndex和endIndex是待分割区间,每次分割之后要把上次的path弹出,比如aab 如果切分a|ab path里面就是a ab再次切割需要吧ab弹出i+1这样就可以切割成a|a|b

public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
Stack<String> path = new Stack<>();
dfs(s, 0, s.length(), path, result);
return result;
}

private void dfs(String s, int startIndex, int endIndex, Stack<String> path, List<List<String>> result) {
if (startIndex == endIndex) {
result.add(new ArrayList(path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (!isPar(s, startIndex, i)) {
continue;
}
path.push(new String(s.toCharArray(), startIndex, i + 1 - startIndex));
dfs(s, i + 1, endIndex, path, result);
path.pop();
}
}

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

发表评论

邮箱地址不会被公开。 必填项已用*标注