[Leetcode] 131. Palindrome Partitioning 解题报告

xiaoxiao2021-02-27  364

题目:

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

Return all possible palindrome partitioning of s.

For example, given s = "aab", Return

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

思路:

凡是涉及到求所有可能的结果集合的问题,99%会用到回溯。本题就是一个典型的回溯问题:我们从某个位置start开始,检查从start开始的所有子字符串是否是回文串,如果是,则加入临时结果中,并且递归求解,一旦搜索到结尾,就说明找到了一个符合条件的解,加入集合即可。当然关键在于递归完成一个子字符串之后的回溯,也就是下面代码中p.pop_back()这关键一句。

另外我发现在下面代码中,参数p采用引用比直接用值效率高很多,这是因为如果用值,将会涉及大量的vector复制操作。所以在回溯问题中,能用引用的就尽量用引用,以提高代码执行效率。

代码:

class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> ret; if(s.length() == 0) { return ret; } vector<string> line; partition(s, ret, line, 0); return ret; } private: void partition(string& s, vector<vector<string>>& result, vector<string> &p, int start) { if(start == s.length()) { result.push_back(p); return; } for(int i = start; i < s.length(); ++i) { if(isPalindrome(s, start, i)) { p.push_back(s.substr(start, i - start + 1)); partition(s, result, p, i + 1); p.pop_back(); } } } bool isPalindrome(string& s, int left, int right) { int i = left, j = right; while(i < j) { if(s[i] != s[j]) return false; ++i, --j; } return true; } };

转载请注明原文地址: https://www.6miu.com/read-798.html

最新回复(0)