首页 > > 程序设计 > C/C++ >

lincode 680 Split String

2018-06-17 21:50:25来源：未知阅读 ()

Split String

描述
笔记
数据
评测

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.

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

Yes

样例

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

这道题目刚一开始我想的就是第一点，可后来发现并不需要。现在感觉能用void就用void，过多的返回值不晕才怪。

1.看到题目给定的函数返回类型是一个嵌套vector，所以很容易的会想到另外设计一个解决函数且返回类型是vector。

2.回溯法的题目必定需要恢复现场，这道题目要考虑的就是怎么恢复现场。

3.考虑嵌套vector什么时候进行插入，考虑插入条件。

4.注意当s.size()==0时怎么操作

下面是没有进行再次优化的代码，有错误或者改进请大佬指出。

class Solution {
public:
    /*
     * @param : a string to be split
     * @return: all possible split string array
     */
    vector <string> a;
    vector<vector<string> > ans;
    void back(int t,int n,string &s)
    {
        if(!s.size())
            {
                ans.push_back(a);
                return ;
            }
        if(t>=s.size())     
        　　return ;
        else{
            if(n==1){
                string c="";
                c=c+s[t];
                a.push_back(c);
                if(t+1==s.size()){
                    ans.push_back(a);
                }
                t++;
                back(t,1,s);
                t++;
                back(t,2,s);
                t-=2;
                a.erase(a.end()-1);
            }
            else{
                string c="";
                c=c+s[t-1]+s[t];
                a.push_back(c);
                if(t+1==s.size()){
                    ans.push_back(a);
                }
                t++;
                back(t,1,s);
                t++;
                back(t,2,s);
                t-=2;
                a.erase(a.end()-1);
            }
            
            
        }
    return ;    
    }
    vector<vector<string> > splitString(string& s) {
        // write your code here
        
        back(0,1,s);
        if(s.size()>1)
            back(1,2,s);
        return ans;
    }
};

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有