Re: [閒聊] 每日leetcode已回收
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/05/22 11:46)推噓4(4推 0噓 2→)留言6則, 5人參與討論串261/1554 (看更多)
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
推
05/22 11:47,
1年前
, 1F
05/22 11:47, 1F
推
05/22 11:49,
1年前
, 2F
05/22 11:49, 2F
推
05/22 11:49,
1年前
, 3F
05/22 11:49, 3F
推
05/22 11:51,
1年前
, 4F
05/22 11:51, 4F
→
05/22 11:54,
1年前
, 5F
05/22 11:54, 5F
→
05/22 11:55,
1年前
, 6F
05/22 11:55, 6F
討論串 (同標題文章)
完整討論串 (本文為第 261 之 1554 篇)：