js 判断回文字符串

zhkai 发布于2019-08-23 11:38 / 836人阅读

摘要：问题描述判断给定的字符串，如果字符串是一个，那么返回，反之返回。第一次不同可允许第一次发现不同时，让右边或左边判断相不相等这时候若相等可继续否则直接返回结果判断字符回文

回文( Palindromes )，在中文文当中是指倒着念和顺着念都是相同的，前后对称，例如“上海自来水来自海上”；在英文文当中是指正着看和反着看都相同的单词，例如“madam”；而对于数字，又称之为回文数，是指一个像“16461”这样的对称的数，即这个数的数字按相反的顺序重新排列后得到的数和原来的数一样。

问题描述

判断给定的字符串，如果字符串是一个Palindromes，那么返回true，反之返回false。

实现方法 1. reverse()

function Palindromes(str) {
    let reg = /[W_]/g; // w 匹配所有字母和数字以及下划线； W与之相反； [W_] 表示匹配下划线或者所有非字母非数字中的任意一个；/g全局匹配
    let newStr = str.replace(reg, "").toLowerCase();
    let reverseStr = newStr.split("").reverse().join("")
    return reverseStr === newStr; // 与 newStr 对比
}

实际上这里做了很多步对数组的操作，字符转数组翻转数组再转字符串，所以这里性能也不是很好。以为数组是引用类型，要改变这个数组，需要开辟新的堆地址空间。

2. for 循环

function Palindromes(str) {
    let reg = /[W_]/g;
    let newStr = str.replace(reg, "").toLowerCase();
    for(let i = 0, len = Math.floor(newStr.length / 2); i < len; i++) {
        if(newStr[i] !== newStr[newStr.length - 1 - i]) return false;
    }
    return true;
}

写法二

function Palindromes(str) {
    let reg = /[W_]/g;
    let newStr = str.replace(reg, "").toLowerCase();
    let len = newStr.length;
    for(let i = 0, j = len - 1; i < j; i++, j--) { // i < j
        console.log("---");
        if(newStr[i] !== newStr[j]) return false;
    }
    return true;
}

3. 递归

function palin(str) {
    let reg = /[W_]/g;
    let newStr = str.replace(reg, "").toLowerCase();
    let len = newStr.length;
    while(len >= 1) {
        console.log("--")
        if(newStr[0] != newStr[len - 1]) {
            // len = 0; // 为了终止 while 循环 否则会陷入死循环
            return false;
        } else {
            return palin(newStr.slice(1, len - 1)); 
        // 截掉收尾字符 再次比较收尾字符是否相等 
        // 直到字符串剩下一个字符（奇数项）或者 0 个字符（偶数项）
        }
    }
    return true;
}

给题目再增加个要求

对于给定的字符串，最多可以删除一个字符，判断它是否还是不是回文。

设置一个变量 flag，当第一次发现两边这一对字符不同时，可继续进行对比; 之后的对比中若发现不同，立即返回结果。

function palin(str) {
    let flag = false; // 第一次不同可允许
    let len = str.length;
    for(let [i, j] = [0, len - 1]; i < j; i++, j--) {
        if(str[i] !== str[j]) {
            if(flag) {
                return false;
            }
            // 第一次发现不同时，让右边-1 或左边+1判断相不相等 
            // 这时候若相等可继续 否则直接返回结果 false
            if(str[i++] == str[j]) {
                i++;
                flag = true;
            } else if (str[i] == str[j--]) {
                j--;
                flag = true;
            } else {
                return false;
            }
        }
    }
    return true;
}

palin("abaacaaa");
palin("aabsdjdbaa");
palin("ab")

references

判断字符回文

云服务器 GPU云服务器判断回文字符c语言 js判断字符串回文的判断c语言回文字符串

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97235.html

LeetCode - 009 - 回文数（palindrome-number）

摘要：最后，我们判断一开始的两种情况，并返回或者即可。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-05-22 19:30:42 Recently revised in 2019-05-23 11:42:52 一目录不折腾的前端，和咸鱼有什么区别目录一目录二前言三解题 3.1 解题 - 数组操作 ...

hikui 2019-05-23 16:23 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
不使用任何额外变量判断回文数字

摘要：不使用任何额外变量判断回文数字思路不能使用额外的变量，只能用参数完成，由于不能使用额外变量的限制，所以代码可读性有点差将转成，利用求出整数的位数，然后用字符串的切片来取得前后对称部分，如为则为，的下标为利用切片可以快速字符串则为可以通过不使用任何额外变量判断回文数字 Palindrome Number Determine whether an integer is a palind...

ad6623 2019-07-25 12:03 评论0 收藏0
[Leetcode] Palindrome Permutation 回文变换

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判断回文的方法来判断结果中是否有回文。而中心对称点如果是字符，该字符会是奇数次，如果在两个字符之间，则所有字符都是出现偶数次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

svtter 2019-08-14 12:36 评论0 收藏0
获取最长回文子串

摘要：以下是最长回文子串的相关代码，相关逻辑已在注释中注明我们原有的字符串可能存在两种回文子串，一种是具有基数个元素例如一种是具有偶数个元素例如这样的话分情况判断比较复杂所以我们对原字符串进行扩充在相邻元素中插入特殊值插入后的原基数回文子串变成了以下是最长回文子串的Manacher‘s Algorithm相关代码，相关逻辑已在注释中注明： public static String solu...

ymyang 2019-08-19 11:46 评论0 收藏0