本文共 916 字,大约阅读时间需要 3 分钟。
题目:
解答:
深搜
代码:
class Solution {public: vector> partition(string s) { int mark[300]; vector > result; DFS(s, s, mark, 0, result); return result; } void DFS(string orgin, string s, int mark[], int len, vector< vector > &result) { if (s == "") { string s1 = ""; string s2 = orgin; vector res; for (int j = 0; j < len; j++) { s1 = s2.substr(0, mark[j]); res.push_back(s1); s2 = s2.substr(mark[j], s2.size() - mark[j]); } result.push_back(res); } else { int i; for (i = 1; i <= s.length(); i++) { string tempstr; tempstr = s.substr(0, i); if (ispalindrome(tempstr)) { mark[len] = i; tempstr = s.substr(i, s.length() - i); DFS(orgin, tempstr, mark, 1+len, result); } } } }private: bool ispalindrome(string s) { int begin = 0; int end = s.length() - 1; while (begin < end) { if (s[begin] != s[end]) return false; else { ++begin; --end; } } return true; }};
转载地址:http://sutsi.baihongyu.com/