lintcode 680. 分割字符串 dfs

浅浅的花香味﹌ 2023-05-22 06:41 2阅读 0赞

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

样例
    样例1
    
    输入： "123"
    输出： [["1","2","3"],["12","3"],["1","23"]]
    样例2
    
    输入： "12345"
    输出： [["1","23","45"],["12","3","45"],["12","34","5"],["1","2","3","45"],["1","2","34","5"],["1","23","4","5"],["12","3","4","5"],["1","2","3","4","5"]]

思路：简单的深度搜索，每一个字符要么自成一个字符串进行递归，要么就和下一个字符组成字符串进行递归即可

class Solution {
        
    public:
        /*
         * @param : a string to be split
         * @return: all possible split string array
         */
        vector<vector<string>> splitString(string& s) {
        
            // write your code here
            vector<vector<string>> res;
            dfs(s,res,vector<string>(),0);
            return res;
        }
        void dfs(string& s, vector<vector<string>> &res,vector<string> tmp,int index)
        {
        
            if(index>=s.size()){
        
                res.push_back(tmp);return;
            } 
            else
            {
        
                string t="";
                t+=s[index];
                tmp.push_back(t);
                dfs(s,res,tmp,index+1);
                tmp.pop_back();
                if(index+1<s.size())
                {
        
                    t+=s[index+1];
                    tmp.push_back(t);
                    dfs(s,res,tmp,index+2);
                }
            }
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode 779. 广义缩写dfs

请完成一个能够给出 wordword 的所有“缩写”的函数（给出任意一种排列即可）样例例1: 输入: word = "word

你的名字/ 2023年05月22日 22:20/ 0 赞/ 1 阅读

相关 lintcode 680. 分割字符串 dfs

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

浅浅的花香味﹌/ 2023年05月22日 06:41/ 0 赞/ 3 阅读

相关【LeetCode 680】验证回文字符串 Ⅱ

题目描述给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例 1: 输入: "aba" 输出: True 示例 2:

谁借莪１个温暖的怀抱￠/ 2023年02月16日 04:16/ 0 赞/ 104 阅读

相关 680. 验证回文字符串 Ⅱ

题目： [680. 验证回文字符串 Ⅱ][680. _] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow

小鱼儿/ 2022年12月07日 12:13/ 0 赞/ 229 阅读

相关 LeetCode 680. 验证回文字符串

680. 验证回文字符串 Ⅱ 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例 1: 输入: "aba" 输出: Tru

我会带着你远行/ 2022年11月07日 11:36/ 0 赞/ 208 阅读

相关 680. 验证回文字符串 Ⅱ

> 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 > > 示例 1: > > 输入: "aba" > 输出: True > 示例 2: >

逃离我推掉我的手/ 2022年10月07日 01:52/ 0 赞/ 234 阅读

相关 680验证回文字符串 Ⅱ

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

淡淡的烟草味﹌/ 2022年09月04日 06:45/ 0 赞/ 239 阅读

相关 LeetCode680. 验证回文字符串 Ⅱ

给定一个非空字符串 `s`，最多删除一个字符。判断是否能成为回文字符串。示例 1: 输入: "aba" 输出: True 示例 2: 输入:

心已赠人/ 2022年05月21日 13:20/ 0 赞/ 269 阅读

相关【LeetCode】680. 验证回文字符串 Ⅱ

题目链接：[https://leetcode-cn.com/problems/valid-palindrome-ii/description/][https_leetcode-

你的名字/ 2022年05月05日 12:30/ 0 赞/ 308 阅读

相关 leetcode680验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出

小灰灰/ 2021年11月17日 04:00/ 0 赞/ 371 阅读