[leetcode] 131. Palindrome Partitioning

[leetcode] 131. Palindrome Partitioning

Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input:

"aab"

Output:

[ ["aa","b"], ["a","a","b"]]

分析

题目的意思是：给定一个字符串s，然后分解成若干个字串，使得每个字串都是回文子串，返回所有可能的形式。

如果是输出所有可能的状态的话，就要用到深度优先搜索，截取一个子串，然后判断是否为回文子串，如果是，加入path表中，然后深度继续寻找。常规解法，一定要会。

代码

class Solution { public: vector> partition(string s) { vector> res; vector out; dfs(s,0,out,res); return res; } void dfs(string s,int start,vector &out,vector>&res){ if(start==s.size()){ res.push_back(out); return; } for(int i=start;i

参考文献

​​[编程题]palindrome-partitioning​​​​[LeetCode] Palindrome Partitioning 拆分回文串​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。