680. 分割字符串

描述

给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果

您在真实的面试中是否遇到过这个题？   是

样例

给一个字符串"123"返回[["1","2","3"],["12","3"],["1","23"]]

类似于111题的爬楼梯问题，使用递归选择一个或者两个

class Solution { public: /* * @param : a string to be split * @return: all possible split string array */ vector<vector<string>> splitString(const string& s) { // write your code here auto skip1 = s.length() > 1 ? splitString(s.substr(1)) : vector<vector<string>>(); auto skip2 = s.length() > 2 ? splitString(s.substr(2)) : vector<vector<string>>(); if (s.length() == 1) skip1.push_back(vector<string>()); if (s.length() == 2) skip2.push_back(vector<string>()); for (auto &vec : skip1) { vec.insert(vec.begin(), s.substr(0, 1)); } for (auto &vec : skip2) { vec.insert(vec.begin(), s.substr(0, 2)); } copy(skip2.begin(), skip2.end(), back_inserter(skip1)); if (skip1.empty()) skip1.push_back(vector<string>()); return skip1; } };