最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

焦点!【LeetCode回溯算法#05】分割回文串(复习双指针判断回文以及substr函数使用记录)

来源:博客园

分割回文串

力扣题目链接


(资料图片仅供参考)

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

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

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

思路

题意很好理解

这里主要有两个问题:

​1、怎么去切割字符串(即切割的方式)

​2、怎么判断回文

切割字符串

第一个问题老生常谈了,用for有局限性,所以用回溯

对照一下前面应用回溯来找组合的操作:

(组合)选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....。

(切割)切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....。

其实本质上是一样的

虽然说是这么说,但实际上是哪个东西执行的“切”这个动作呢?

因为我们需要指定遍历位置,因此和之前的问题一样需要使用beginIndex

而这个beginIndex就是“切割线”

例如:

在单层处理时,我们需要使用for来遍历字符串嘛,就有以下情况:

aabaa↑  ↑bI i

因为在初始化for的条件时,i是等于beginIndex的,经过循环,i会不断自增,相当于“切割线”不断右移

每次遍历,我们将当前字符串s的[beginIndex, i]区间输入给一个回文判断函数

若当前区间代表的子串是回文串,那么就使用substr函数将其截取下来保存

题外话:substr函数

该函数的简介

其输入是一个区间,举个例子:

test_str = "abb";test_str.substr(0, 1);//cout->"a"test_str.substr(0, 2);//cout->"ab"test_str.substr();//cout->"abb"

可见,substr获取的子串是左闭右开的,即右边界的元素不获取

判断回文串

双指针法,没什么好说的

将待判断的子串的区间传入,作为遍历时的左右指针,然后遍历判断即可

//回文判断函数    bool isPalindrome(string& s, int start, int end){        //双指针遍历        for(int i = start, j = end; i < j; ++i, --j){            if(s[i] != s[j]){                return false;            }        }        return true;    }

代码

还是按回溯三部曲来写,直接给出代码了

有问题的地方详见注释

class Solution {private:    //定义回文判断函数    bool isPalindrome(string& s, int start, int end){        //双指针遍历        for(int i = start, j = end; i < j; ++i, --j){            if(s[i] != s[j]){                return false;            }        }        return true;    }    //定义结果数组    vector> res;    vector path;    //确定回溯函数的参数和返回值    void backtracking(string& s, int beginIndex){        //确定终止条件        //如果起始位置已经大于s的大小,说明已经找到了一组分割方案了        if(beginIndex >= s.size()){            res.push_back(path);            return;        }        //确定单层处理逻辑        for(int i = beginIndex; i < s.size(); ++i){            //判断当前串是否为回文串            if(isPalindrome(s, beginIndex, i)){//是回文串                //获取s中从beginIndex到当前切割位置的子串                //使用substr函数                //i - beginIndex + 1是当前"切割线"的位置                string cutStr = s.substr(beginIndex, i - beginIndex + 1);                path.push_back(cutStr);            }else{                continue;//不是回文串就跳过            }            backtracking(s, i + 1);//递归            path.pop_back();//回溯        }    }public:    vector> partition(string s) {        backtracking(s, 0);        return res;    }};

关键词: