一次过
1 class Solution { 2 public: 3 bool check(string s) { 4 for (int i = 0; i < s.size(); i++) { 5 if (s[i] != s[s.size()-1-i]) return false; 6 } 7 return true; 8 } 9 void dfs(vector<vector<string>> &ret, vector<string> &retin, string s, int beg, int size) { 10 if (beg == size) ret.push_back(retin); 11 for (int i = 1; i <= size-beg; i++) { 12 if (check(s.substr(beg, i))) { 13 retin.push_back(s.substr(beg, i)); 14 dfs(ret, retin, s, beg+i, size); 15 retin.pop_back(); 16 } 17 } 18 } 19 vector<vector<string>> partition(string s) { 20 // Start typing your C/C++ solution below 21 // DO NOT write int main() function 22 vector<vector<string>> ret; 23 vector<string> retin; 24 dfs(ret, retin, s, 0, s.size()); 25 return ret; 26 } 27 };
C#
1 public class Solution { 2 public List<List<string>> Partition(string s) { 3 List<List<string>> ans = new List<List<string>>(); 4 List<string> tmp = new List<string>(); 5 dfs(ref ans, ref tmp, s, 0, s.Length); 6 return ans; 7 } 8 public void dfs(ref List<List<string>> ans, ref List<string> tmp, string s, int beg, int size) { 9 if (beg == size) { 10 List<string> local = new List<string>(tmp.ToArray()); 11 ans.Add(local); 12 } 13 for (int i = 1; i <= size - beg; i++) { 14 if (check(s.Substring(beg, i))) { 15 tmp.Add(s.Substring(beg, i)); 16 dfs(ref ans, ref tmp, s, beg+i, size); 17 tmp.RemoveAt(tmp.Count-1); 18 } 19 } 20 } 21 public bool check(string s) { 22 for (int i = 0; i < s.Length; i++) { 23 if (s[i] != s[s.Length-1-i]) return false; 24 } 25 return true; 26 } 27 }