38 - 验证回文串

题目

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

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

示例 1:

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

示例 2:

输入: "race a car"

输出: false

解答

反转字符串

想法就是，用正则把空格、标点都删掉，然后全改成小写，看前后是不是匹配

怎么看前后是不是匹配呢？有一道题叫“回文数”，思路是一样的。

原来的方法是再造一个数组，反转了字符串的后半部分，然后一个个对比。

var isPalindrome = function (s) {
  if (!s) {
    return true
  }
  s = s.replace(/[\ |\~|\`|\!|\@|\#|\$|\%|\^|\&|\*|\(|\)|\-|\_|\+|\=|\||\\|\[|\]|\{|\}|\;|\:|\"|\'|\,|\<|\.|\>|\/|\?]/g, "").toLowerCase();


  const half = Math.round(s.length / 2);
  const reverseStr = s
    .slice(half - 1)
    .split("")
    .reverse()
    .join("");
  for (let i = 0; i < half; i++) {
    if (s[i] !== reverseStr[i]) {
      return false;
    }
  }
  return true;
};

Runtime: 80 ms, faster than 38.77% of JavaScript online submissions for Valid Palindrome.

Memory Usage: 37.2 MB, less than 74.19% of JavaScript online submissions for Valid Palindrome.

双指针

var isPalindrome = function (s) {
  if (!s) {
    return true
  }
  s = s.replace(/[\ |\~|\`|\!|\@|\#|\$|\%|\^|\&|\*|\(|\)|\-|\_|\+|\=|\||\\|\[|\]|\{|\}|\;|\:|\"|\'|\,|\<|\.|\>|\/|\?]/g, "").toLowerCase();

  let first = 0
  last = s.length - 1
  while (first < last) {
    if (s[first] !== s[last]) {
      return false
    }
    first++
    last--
  }
  return true
};

Runtime: 84 ms, faster than 27.35% of JavaScript online submissions for Valid Palindrome.

Memory Usage: 37 MB, less than 80.65% of JavaScript online submissions for Valid Palindrome.

优化

作者：wo-sha-du-bu-hui-2

链接：https://leetcode-cn.com/problems/two-sum/solution/javascriptshi-xian-by-wo-sha-du-bu-hui-2/

原来的做法是把所有的标点和空格都去掉，他的做法是只留下字母和数字。

...
    s = s.replace(/[^A-Za-z0-9]/g, "").toLowerCase();
...

反转字符串

Runtime: 64 ms, faster than 91.55% of JavaScript online submissions for Valid Palindrome.

Memory Usage: 37.3 MB, less than 73.66% of JavaScript online submissions for Valid Palindrome.

双指针

Runtime: 68 ms, faster than 82.62% of JavaScript online submissions for Valid Palindrome.

Memory Usage: 37 MB, less than 81.18% of JavaScript online submissions for Valid Palindrome.

两个都快了不少。

不过他的评价做法是新建一个字符串，反转，并比较是否相等。很浪费资源就是了

...
return s == s.split('').reverse().join('')

Runtime: 76 ms, faster than 53.79% of JavaScript online submissions for Valid Palindrome.

Memory Usage: 38.2 MB, less than 48.93% of JavaScript online submissions for Valid Palindrome.

go

作者：elliotxx 链接：https://leetcode-cn.com/problems/two-sum/solution/4mstou-wei-zhi-zhen-de-go-shi-xian-by-elliotxx/

func isPalindrome(s string) bool {
    if s == "" {
        return true
    }
    s = strings.ToLower(s)
    first, last := 0, len(s)-1
    for first < last {
        if !('a' <= s[first] && s[first] <= 'z' || '0' <= s[first] && s[first] <= '9') {
            first++
            continue
        }
        if !('a' <= s[last] && s[last] <= 'z' || '0' <= s[last] && s[last] <= '9') {
            last--
            continue
        }
        if s[first] != s[last] {
            return false
        }
        first++
        last--
    }
    return true
}

Runtime: 4 ms, faster than 73.49% of Go online submissions for Valid Palindrome.

Memory Usage: 3 MB, less than 62.07% of Go online submissions forValid Palindrome.

研究了一下这个代码，有几个收获：

• 第六行，定义指针可以两个一起定义

• 处理字符串的方法，本来想用正则，结果会有很多strings.Replace()，感觉没这个比较的方法好。

go的测试环境

package main

import (
    "fmt"
    "runtime"
    "strings"
)

type Test struct {
    inputs string
    target bool
}

func ensure(ans, target bool, index int) {
    if ans != target {
        WrongMsg(ans, target, index)
    }
}

func WrongMsg(ans, target bool, index int) {
    fmt.Println("*** wrong", index)
    fmt.Println("* target", target)
    fmt.Println("* ans", ans)
}

func isPalindrome(s string) bool {
    if s == "" {
        return true
    }
    s = strings.ToLower(s)
    first, last := 0, len(s)-1
    for first < last {
        if !('a' <= s[first] && s[first] <= 'z' || '0' <= s[first] && s[first] <= '9') { // 只处理字母和数字
            first++
            continue
        }
        if !('a' <= s[last] && s[last] <= 'z' || '0' <= s[last] && s[last] <= '9') {
            last--
            continue
        }
        if s[first] != s[last] {
            return false
        }
        first++
        last--
    }
    return true
}

func main() {
    DATA := [3]Test{
        {
            inputs: "A man, a plan, a canal: Panama",
            target: true,
        },
        {
            inputs: "race a car",
            target: false,
        },
        {
            inputs: "",
            target: true,
        },
    }
    for i, elem := range DATA {
        test := elem.inputs
        ans := isPalindrome(test)
        target := elem.target
        ensure(ans, target, i)
        runtime.Gosched()
    }
}