推 JIWP: 別卷了 05/22 11:47
推 SecondRun: 教我 05/22 11:49
推 DJYOSHITAKA: 別卷了 05/22 11:49
推 digua: 大師 05/22 11:51
→ sustainer123: 二跑哪段不懂?這題就從單個元素回溯變片段回溯 05/22 11:54
→ JIWP: backtracking好難 05/22 11:55
https://leetcode.com/problems/palindrome-partitioning
131. Palindrome Partitioning
回傳所有可以拆成數個子字串且全是回文的組合
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
思路:
1.確認子字串是否為回文
2.backtracking
Python Code:
class Solution:
def partition(self, s: str) -> List[List[str]]:
def is_palindrome(l, r):
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
def backtrack(start, path):
if start == len(s):
res.append(path[:])
return
for end in range(start, len(s)):
if is_palindrome(start, end):
path.append(s[start:end + 1])
backtrack(end + 1, path)
path.pop()
res = []
backtrack(0, [])
return res
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.130.118 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716349604.A.BE2.html