125 - 验证回文串(valid-palindrome)

Create by jsliang on 2019-7-2 07:50:41
Recently revised in 2019-7-2 08:57:36

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解法 - 暴力破解
3.2 解法 - 双指针

二 前言

返回目录

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

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

示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:
输入: "race a car"
输出: false

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - 暴力破解

返回目录

  • 解题代码
var isPalindrome = function(s) {
  s = s.replace(/[^0-9a-zA-Z]/g, '').toLocaleLowerCase();
  let reverse = s.split('').reverse().join('');
  return s === reverse;
};
  • 执行测试

  • sA man, a plan, a canal: Panama

  • returntrue

  • LeetCode Submit

√ Accepted
  √ 476/476 cases passed (96 ms)
  √ Your runtime beats 95.55 % of javascript submissions
  √ Your memory usage beats 42.1 % of javascript submissions (38.3 MB)
  • 知识点

  • replace()replace()方法返回一个由替换值(replacement)替换一些或所有匹配的模式(pattern)后的新字符串。模式可以是一个字符串或者一个正则表达式,替换值可以是一个字符串或者一个每次匹配都要调用的回调函数。replace() 详细介绍

  • toLocaleLowerCase()toLocaleLowerCase()方法根据任何特定于语言环境的案例映射,返回调用字符串值转换为小写的值。。toLocaleLowerCase() 详细介绍
  • split()split() 方法使用指定的分隔符字符串将一个 String 对象分割成字符串数组,以将字符串分隔为子字符串,以确定每个拆分的位置。split() 详细介绍
  • reverse()reverse() 方法将数组中元素的位置颠倒,并返回该数组。该方法会改变原数组。reverse() 详细介绍
  • join()join() 方法将一个数组(或一个类数组对象)的所有元素连接成一个字符串并返回这个字符串。join() 详细介绍

  • 解题思路

暴力破解,无疑是最不耗脑力的,你只需要知道几个 JS 的 API 即可:

首先,规整字符串:

s = s.replace(/[^0-9a-zA-Z]/g, '').toLocaleLowerCase();

  • replace():将 s 中非大小写字符或者数字的内容替换掉。
  • toLocaleLowerCase:将字符串转成小写。

此时,s = amanaplanacanalpanama

然后,将字符串转成数组,调用数组的 reverse(),再将数组换成字符串:

let reverse = s.split('').reverse().join('');

  • split():将字符串转成数组
  • reverse():反转数组
  • join():将数组转成字符串

最后,判断下 s === reversereturn 这个结果值即可。

3.2 解法 - 双指针

返回目录

  • 解题代码
var isPalindrome = function(s) {
  s = s.replace(/[^0-9a-zA-Z]/g, "").toLocaleLowerCase();
  for (let i = 0; i < s.length / 2; i++) {
    if (s[i] !== s[s.length - 1 - i]) {
      return false;
    }
  }
  return true;
};
  • 执行测试

  • sA man, a plan, a canal: Panama

  • returntrue

  • LeetCode Submit

√ Accepted
  √ 476/476 cases passed (92 ms)
  √ Your runtime beats 97.57 % of javascript submissions
  √ Your memory usage beats 75.72 % of javascript submissions (37.1 MB)
  • 解题思路

首先,国际惯例去掉非大小写字符或者数字的字符串,并将字符串转换成小写。

然后,我们对字符串进行一个遍历(有的小伙伴可能不知道,JS 字符串也可以通过 for 遍历,但是听说字符串的遍历会比数组的遍历消耗多点)。

由于是判断回文,所以我们只需要循环一半即可(如果长度为 3/5/7 等奇数值,忽略中间那个字符串,例如 abcba,忽略 c 也是可行的)。

if (s[i] !== s[s.length - 1 - i]) {
  return false;
}

最后,我们通过双指针的移动:

0 1 2 3 4 a b c b a

  • 0 对应着 length - 1 - 0 = 4
  • 1 对应着 length - 1 - 1 = 3
  • 2 对应着 length - 1 - 2 = 2

这样,当它们对应的数字不同时,返回 false;否则返回 true


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-02 18:49:32

results matching ""

    No results matching ""