推 pandix: 大師 01/22 10:59
推 PogChampLUL: 大師 初一也要刷題 01/22 11:01
推 SecondRun: 大師 01/22 11:02
131. Palindrome Partitioning
給你一個字串s，我們可以把字串切分，找出所有可以讓字串s的子字串都是迴文的切法。
Example :
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
思路：
1.很直觀的解法，從當前點往後不斷的把當前點為起點的字串變長，然後如果切完的子
字串是迴文就繼續DFS下去。
2.如果start到底表示當前切法的子字串都是迴文字串，加入res。
Java Code：
---------------------------------------------
class Solution {
private List<List<String>> res;
public List<List<String>> partition(String s) {
res = new ArrayList<>();
backTracking(s, new ArrayList<>(), 0);
return res;
}
private void backTracking(String s, List<String> curr, int start) {
if (start == s.length()) {
res.add(new ArrayList<>(curr));
}
for (int i = start; i < s.length(); i++) {
String partition = s.substring(start, i + 1);
if (isPalindrome(partition)) {
curr.add(partition);
backTracking(s, curr, i + 1);
curr.remove(curr.size() - 1);
}
}
}
private boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l++) != s.charAt(r--)) return false;
}
return true;
}
}
---------------------------------------------
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674356230.A.81A.html