【3.7】LeetCode每日一题· 分割回文串

2021年03月07日 13时32分

标签： LeetCode dfs 动态规划

## 题目描述
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
返回s所有可能的分割方案。

#### 示例
	输入: "aab"
	输出:
	[
	  ["aa","b"],
	  ["a","a","b"]
	]

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接]

## 解题思路
由于需要求出字符串**s**的所有分割方案，因此考虑使用深度优先搜索解决。

如果我们需要求`s[l..r]`的分割方案，假设已经知道`s[i..j]（包含s[j]）`内的所有分割方案，那么只要求得`s[j+1..r]`子串的分割方案，即可得出答案。

因此，我们从**l**开始找到第一个回文串的右边界**i**，将其加入答案中，然后递归地找到剩余子串的所有分割方法，直到**l**等于**s**的长度为止，将当前答案插入最后的答案集中；接着，找到第二个回文串的右边界……以此类推直到右边界**i**等于**s**的长度为止。

那么问题就变为，**如何判断一个字符串是回文串？**。针对本题，有三种解法
1. 考虑到回文串从左至右读和从右至左读相同，因此采用双指针，**i**指向字符串开头，**j**指向字符串结尾，判断`s[i]`与`s[j]`是否相同；若相同则**i**后移一位，**j**前移一位，否则说明不是回文串。
2. 上述方法对于本题来说，可能产生多余的计算。例如对于`aaba`，对于前两个字符`aa`，有`[aa]`和`[a], [a]`两种分割方法，那么对于每一种分割方法，当搜索到字符`b`时，都会重复地判断`b`和`ba`是否为回文串。
考虑到回文字符串有如下特性：一个回文字符串去掉头尾字符剩下的一定也是回文字符串，我们可以考虑如下动态规划状态转移方程
$$ dp[i][j] = True, i \leq j $$
$$ dp[i][j] = dp[i+1][j-1] \wedge (s[i]==s[j]) i<j $$
	
	因此可以首先预处理出`s`中的每个子串是否为回文串，在搜索过程中直接判断即可。
3. 进一步优化，考虑到搜索过程中，并不是`s`的每个子串都会被访问，因此采用记忆画搜索即可。

## 代码（朴素DFS）
	class Solution {
	public:
		vector<vector<string>> res;
		vector<string> temp;

bool check(string& s, int l, int r){
			int i = l, j = r;
			while(i < j && s[i] == s[j]){
				i++; j--;
			}
			if(i < j) return false;
			return true;
		}

void dfs(string& s, int l){
			if(l == s.length()){
				res.push_back(temp);
				return;
			}
			string t = "";
			for(int i = l; i < s.length(); i++){
				t.push_back(s[i]);
				if(check(s, l, i)){
					temp.push_back(t);
					dfs(s, i+1);
					temp.pop_back();
				}
			}
		}
		vector<vector<string>> partition(string s) {
			dfs(s, 0);
			return res;
		}
	};

## 代码（DFS+DP预处理）
	class Solution {
	public:
		vector<vector<string>> res;
		vector<string> temp;
		vector<vector<bool>> dp;

void dfs(string& s, int l){
			if(l == s.length()){
				res.push_back(temp);
				return;
			}
			string t = "";
			for(int i = l; i < s.length(); i++){
				t.push_back(s[i]);
				if(dp[l][i]){
					temp.push_back(t);
					dfs(s, i+1);
					temp.pop_back();
				}
			}
		}
		vector<vector<string>> partition(string s) {
			const int N = s.length();
			dp.assign(N, vector<bool>(N, true));
			for(int i = N-1; i >=0 ; --i){
				for(int j = i+1; j < N; j++){
					dp[i][j] = dp[i+1][j-1] && (s[i] == s[j]);
				}
			}
			dfs(s, 0);
			return res;
		}
	};

## 代码（记忆化搜索）
	class Solution {
	public:
		vector<vector<string>> res;
		vector<string> temp;
		vector<vector<int>> dp;

bool check(string& s, int l, int r){
			if(dp[l][r] != -1) return dp[l][r];
			int i = l, j = r;
			while(i < j && s[i] == s[j]){
				i++; j--;
			}
			if(i < j) return dp[l][r] = false;
			return dp[l][r] = true;
		}

#### 用时和内存
> 执行用时：124 ms，在所有 C\++提交中击败了87.45%的用户
> 内存消耗：74.1 MB，在所有 C\++提交中击败了50.96%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.7】LeetCode每日一题· 分割回文串

所有评论

暂无评论

新增评论