来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位同学在字节实习了不到两周就被劝退了，直属leader认为他能力不够，效率也不高，临走前闹的很不愉快，这位同学比较担心leader在系统中对自己有负面评价影响以后求职字节。
刚好评论区有位字节的员工说他也劝退过实习生，系统中只会有是否触犯红线这种选项并不会有长篇评价要写，但如果是面试字节，面试官可以看到之前的面试评价，可能会影响面试官对你的判断。更多的网友觉得这对实习生有点苛刻了，刚入职不到两周应该连环境都没熟悉好。我认为这跟领导的风格应该有很大关系，他可能就是想让你进来就能干活，后面发现你不但干不了活，还要花时间培养你，导致自己的效率都下降了，干脆就劝退了。还有网友开玩笑说被劝退不但会影响你后面进字节，还会影响子女进字节。
言归正传，今天我们来分享一道高频面试题「分割回文串」。
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。
举个例子：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
思路解析
在做这道题之前，你需要掌握如何判断一个字符串为回文串。
这道题的关键是穷举所有的分割点，比如对于字符串s="aab"，它有三个分割点，就是下图中标记为绿色的地方。
我们通过选择不同的分割点可以得到一棵决策树，如下图所示。绿色的节点是满足条件的回文子串，红色的节点不是回文子串。
这是一个回溯问题，通过穷举所有可能的解来寻找满足条件解。采用深度优先搜索，从解空间的一个起始节点出发，沿着一条路径搜索解空间，如果当前路径不可能找到满足条件的解或者当前路径已经是一个满足条件的解时，就回溯到上一个节点，尝试其他的路径。重复这个过程，直到找到所有可能的解，或者解空间被完全搜索。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> tmp;
dfs(s, 0, res, tmp);
return res;
}
//判断s的区间[left, right]是否是回文串
bool isPal(string& s, int left, int right) {
while (left < right) {
if (s[left] == s[right]) {
++left;
--right;
} else {
return false;
}
}
return true;
}
void dfs(string s, int index, vector<vector<string>>& res, vector<string>& tmp) {
//边界条件，当前索引大于等于s的长度，说明搜索到了一个满足条件的分割方案
if (index >= s.length()) {
res.push_back(tmp);
return;
}
//穷举所有可能的分割点
for (int i = index; i < s.length(); ++i) {
if (isPal(s, index, i)) {
//选择一个分割点
tmp.push_back(s.substr(index, i - index + 1));
dfs(s, i + 1, res, tmp);
//撤销前面的选择，回溯尝试其他的分割点
tmp.pop_back();
}
}
}
};
class Solution: def partition(self, s: str) -> List[List[str]]: res = [] tmp = [] self.dfs(s, 0, res, tmp) return res # 判断s的区间[left, right]是否是回文串 def is_pal(self, s: str, left: int, right: int) -> bool: while left < right: if s[left] == s[right]: left += 1 right -= 1 else: return False return True def dfs(self, s: str, index: int, res: list[list[str]], tmp: list[str]): # 边界条件，当前索引大于等于s的长度，说明搜索到了一个满足条件的分割方案 if index >= len(s): res.append(tmp[:]) return # 穷举所有可能的分割点 for i in range(index, len(s)): if self.is_pal(s, index, i): # 选择一个分割点 tmp.append(s[index:i+1]) self.dfs(s, i + 1, res, tmp) # 撤销前面的选择，回溯尝试其他的分割点 tmp.pop()
时间复杂度： 时间复杂度跟决策树中的节点数有关。
空间复杂度： 这里用到了递归，递归会用到函数栈，递归的深度跟决策树的高度有关，所以空间复杂度也跟决策树的高度有关。
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
