【LeetCode】131. Palindrome Partitioning 解題報告
131. Palindrome Partitioning / Medium
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.
Example 1:
Input: s = “aab”
Output: [[“a”,”a”,”b”],[“aa”,”b”]]
Example 2:
Input: s = “a”
Output: [[“a”]]
Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters.
Solution 1: Backtracking
思路
用 DFS 做 backtracking,窮舉所有的可能性。
對於長度為 N 的字串來說,會展開 2^N 個節點,而每次 DFS 都需要用 O(N) 產生並判斷是否是迴文,所以時間複雜度為 O(N*2^N)
效能
Complexity
- Time Complexity: O(N*2^N)
- Space Complexity: O(N)
LeetCode Result
- Runtime: 113 ms
- Memory Usage: 49 MB
- https://leetcode.com/submissions/detail/731656338/
Code
1 | class Solution { |
Solution 2: Backtracking + DP
思路
由於每次都要判斷是不是迴文會損失很多時間,我們利用 DP 來儲存並判斷子字串是否是迴文。
如果目前兩字元相等,而且向內(dp[start+1][end-1])是迴文,那這個字串就是迴文。
但要注意前後相減小於等於 2 的狀態,會觸及邊界。
效能
Complexity
- Time Complexity: O(N*2^N)
- Space Complexity: O(N^2)
LeetCode Result
- Runtime: 98 ms
- Memory Usage: 49.2 MB
- https://leetcode.com/submissions/detail/731659644/
Code
1 | class Solution { |