原题

LintCode 680. Split String

Description

Give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. Output all possible results.

Example

Given the string "123"
return [["1","2","3"],["12","3"],["1","23"]]

解题

题意为，给定一串字符串，分割为若干个子串。每个字串应该为一个单独的字符，或者相邻的两个字符组成的子串。给出所有可能的结果。

类似于爬梯问题，每次可以爬一阶楼梯和两节楼梯，一共有多少种爬法。直接递归调用，第一次只取前一个字符或前两个字符即可。

代码

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;
    }
};