131. Palindrome Partitioning
給定一個字符串 s，將 s 分割，使得分割的每個子字符串都是回文。返回所有可能的回文分割方案。
範例：
輸入：s = "aab" 輸出：[["a","a","b"],["aa","b"]]
Python
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
def is_palindrome(sub: str) -> bool:
return sub == sub[::-1]
def backtrack(start: int, path: List[str]):
if start == len(s):
result.append(path[:])
return
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()
result = []
backtrack(0, [])
return result
35.30MB, 456ms
C++
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
backtrack(s, 0, path, result);
return result;
}
private:
void backtrack(const string &s, int start, vector<string> &path,
vector<vector<string>> &result) {
if (start == s.size()) {
result.push_back(path);
return;
}
for (int end = start; end < s.size(); ++end) {
if (isPalindrome(s, start, end)) {
path.push_back(s.substr(start, end - start + 1));
backtrack(s, end + 1, path, result);
path.pop_back();
}
}
}
bool isPalindrome(const string &s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) {
return false;
}
}
return true;
}
};
52.76MB, 70ms
Javascript
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
const result = [];
const isPalindrome = (str) => {
let left = 0;
let right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
};
const backtrack = (start, path) => {
if (start === s.length) {
result.push([...path]);
return;
}
for (let end = start; end < s.length; end++) {
const substring = s.substring(start, end + 1);
if (isPalindrome(substring)) {
path.push(substring);
backtrack(end + 1, path);
path.pop();
}
}
};
backtrack(0, []);
return result;
};
72.59MB, 201ms
