当前位置 : 主页 > 编程语言 > 其它开发 >

力扣算法:125-验证回文串,131-分割回文串---js

来源:互联网 收集:自由互联 发布时间:2022-05-30
菜鸡刷算法的一天,每天分享两题算法,大家有这个想法的,可以给我个关注,然后一起坚持每天的算法之旅。希望我们共同进步,一起加油。 LC 125-验证回文串 给定一个字符串,验证
菜鸡刷算法的一天,每天分享两题算法,大家有这个想法的,可以给我个关注,然后一起坚持每天的算法之旅。希望我们共同进步,一起加油。 LC 125-验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

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

示例 1:

-输入: "A man, a plan, a canal: Panama"
-输出: true
-解释:"amanaplanacanalpanama" 是回文串
复制代码

示例 2:

- 输入: "race a car"
- 输出: false
- 解释:"raceacar" 不是回文串
复制代码

解题思路 :利用正则表达式去掉字符串中的空格和标点符号,在全部转为小写(大写也行)。然后设立对撞双指针,判断左右两边字符是否相同。

代码:

var isPalindrome = function(s) {
    s = s.replace(/[\W|_]/g, "").toLowerCase(); //去除字符串中的空格与标点符号,并将字符串转为小写
    let i = 0, j = s.length - 1; //设立双指针,一个头指针,一个尾指针
    if(s.length < 2) {    //当字符串长度小于2的时候,直接判断为字符串
        return true;
    }
    while(i < j) {    //当头指针小于尾指针的时候
        if(s[i] != s[j]) {  //两个位置上的字符不一样的话
            return false; //则不是回文串
        }
        // 否则就头指针+1,尾指针-1
        i++;
        j--;
    }
    return true;  //都满足头指针位置上的数都小于尾指针的话,就是回文串
};
复制代码
LC 131-分割回文串

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

s皆为小写字符

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
复制代码

示例 2:

输入:s = "a"
输出:[["a"]]
复制代码

解题思路:通过递归+回溯算法解决。将字符串通过切割线进行分割,然后判断分割出来的字符串是否是回文串,是的话就保存在数组中,不是的话就继续递归进行查找。

代码:

var partition = function(s) {
    var res = [], temp = []; // res保存最后的结果。 temp保存每一层树形结构的结果。
    var start = 0;  //切割线
    
    // 开始执行递归
    partitionFun(s,start,temp,res);
    return res;
};
function partitionFun(s,start,temp,res) {
    // 设定递归终止条件--切割线在字符最后面的时候
    if(start == s.length) {
        res.push([...temp]);
        return;  
    }
​
    // 开始进行一层的遍历
    for(var i = start; i < s.length; i++) {
        // 判断是否是回文串
        if(isPalindrome(s, start,i)) {
            var text = s.substring(start, i + 1); //拿到分割后的子串
            temp.push(text); //将字串放进temp中
            // 进行递归
            partitionFun(s,i + 1,temp,res);
            // 进行回溯
            temp.pop();
        }
    };
};
// 判断是否为回文串
var isPalindrome =  (s, i, j) =>{
    while(i < j) {
        if(s[i] != s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
};
上一篇:多线程07:async、future、packaged_task、promise
下一篇:没有了
网友评论