回溯之分割回文串

题目:

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 

回文串

 。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

难点:这里用到一个很取段的思路,其实和取点的内容差不多,但是取端更难理解。

思路:直接看回溯函数的内容,首先我们是取段的,如果这一段不行那就往后面加1,直到加道循环结束。然后就被pop掉。如果可以取端,并且取到了最后一段,也就是开始的startIndex大于等于size那么就代表这一条都是回文字符串。然后需要一个判断函数,判断字符串是否为回文字符串,如果是往path里面加。

学到的新函数:array.substr( a ,b) a表示字符串的开始,b表示数量   含义:选取字符串array从a开始往后的b个数

看代码:

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path;
    void backtraking(string s,int startIndex)
    {
        if(startIndex > s.size()-1)
        {
            result.push_back(path);
            return;
        }
        for(int i = startIndex;i < s.size();i++)
        {
            if(check(s,startIndex,i))
            {
                string str = s.substr(startIndex,i-startIndex+1);
                path.push_back(str);
            }
            else {continue;}
            backtraking(s,i+1);
            path.pop_back();
        }
    }
    bool check(string s,int a,int b)
    {
        int left = a;
        int right = b;
        for(; left < right; left++,right--)
        {
            if(s[left] != s[right])return false;
        }
        return true;
    }


public:
    vector<vector<string>> partition(string s) 
    {
        backtraking(s,0);
        return result;
    }
};

 

相关推荐

  1. 回溯分割

    2024-06-09 13:22:03       5 阅读
  2. 【算法】分割【动态规划】【回溯

    2024-06-09 13:22:03       28 阅读
  3. 代码随想录二刷 |回溯分割

    2024-06-09 13:22:03       35 阅读
  4. 回溯】Leetcode 131. 分割【中等】

    2024-06-09 13:22:03       12 阅读
  5. 131. 分割

    2024-06-09 13:22:03       29 阅读

最近更新

  1. c++_0基础_讲解5 判断语句

    2024-06-09 13:22:03       0 阅读
  2. 算法训练营day23补签

    2024-06-09 13:22:03       0 阅读
  3. ISO七层模型 tcp/ip

    2024-06-09 13:22:03       0 阅读
  4. 2022C语言二级真题

    2024-06-09 13:22:03       0 阅读
  5. TCP协议参数设置&说明

    2024-06-09 13:22:03       0 阅读

热门阅读

  1. 【环境搭建】2.阿里云ECS服务器 安装MySQL

    2024-06-09 13:22:03       3 阅读
  2. 2 程序的灵魂—算法-2.2 简单算法举例-【例 2.5】

    2024-06-09 13:22:03       4 阅读
  3. 【小海实习日记】金融-现货以及合约理解

    2024-06-09 13:22:03       5 阅读
  4. 【Qt】Item Views与Item Widgets的区别

    2024-06-09 13:22:03       4 阅读
  5. qt自定义事件过滤器

    2024-06-09 13:22:03       3 阅读
  6. liunx查看日志

    2024-06-09 13:22:03       5 阅读
  7. FPGA复位:(43)复位高扇出的解决方案?

    2024-06-09 13:22:03       4 阅读
  8. vue3模板语法总结

    2024-06-09 13:22:03       3 阅读
  9. 用C++做一个跑酷游戏

    2024-06-09 13:22:03       5 阅读
  10. FPGA复位:(41)复位管脚PR报错?

    2024-06-09 13:22:03       4 阅读
  11. 逆运动学IK原理举例说明

    2024-06-09 13:22:03       5 阅读
  12. 浅谈单臂路由

    2024-06-09 13:22:03       4 阅读