Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/01/22 10:57)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串203/719 (看更多)

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