leetcode131. 分割回文串

給定一個(gè)字符串 s，將 s 分割成一些子串，使每個(gè)子串都是回文串。

返回 s 所有可能的分割方案。

示例:

輸入:?"aab"

輸出:

[

["aa","b"],

["a","a","b"]

]

思路：搜索回溯，搜索過(guò)程中檢查是否是回文。

public class Solution {

List> res = new ArrayList<>();

// Stack 這個(gè)類(lèi) Java 的文檔里推薦寫(xiě)成 Deque stack = new ArrayDeque();

// 注意：只使用 stack 相關(guān)的接口

Deque stack = new ArrayDeque<>();

int len;

public List> partition(String s) {

len = s.length();

if (len == 0) return res;

backtracking(s, 0);

return res;

}

private void backtracking(String s, int start) {

if (start == len) {

res.add(new ArrayList<>(stack));

return;

}

for (int i = start; i < len; i++) {

if (checkPalindrome(s, start, i)) {

stack.addLast(s.substring(start, i + 1));

backtracking(s, i + 1);

stack.removeLast();

}

}

}

private boolean checkPalindrome(String str, int left, int right) {

while (left < right) {

if (str.charAt(left) != str.charAt(right)) return false;

left++;right--;

}

return true;

}

}

數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶(hù)投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶(hù)投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。