125. 验证回文串

题目描述（难度：简单）

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

示例1:

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

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

思路1:

去除字符串中的非字符和非数字，然后转成数组，反转。将原字符和新字符比较，看是否相等
详解
- 1.将传入的字符串，利用 toLowerCase() 方法统一转化为小写，再利用正则表达式 /[ ^ A-Za-z0-9]/g 在字符串中去除非字母和数字，得到字符串 arr。
- 2.将字符串 arr 转换为数组，利用数组的方法反转数组，再将数组转为字符串 newArr。
- 3.将字符串 arr 和字符串 newArr 进行比较，相等即为回文串，不相等则不为回文串。

代码1

    /**
    * @param {string} s
    * @return {boolean}
    */
    const isPalindrome = (s) => {
        const newStr = s.toLowerCase().replace(/[^a-zA-Z0-9]/g,'');
        const arr = newStr.split('').reverse().join('');
        return newStr === arr;
    };

复杂度分析1

时间复杂度：O(n)
- 该解法中，toLowerCase(), replace(), split(), reverse(), join() 的时间复杂度都为，且都在独立的循环中执行，因此，总的时间复杂度依然为O(n) 。
空间复杂度：O(n)
- 该解法中，申请了 1 个大小为的字符串和 1 个大小为的数组空间，因此，空间复杂度为，即 O(n)。

思路2:

首先，去除字符串中的非字母和数字，再将字符串转换为数组，再对数组首尾一一比较，即可得出结果。
详解：
- 1.将传入的字符串，利用 toLowerCase() 方法统一转化为小写，再利用正则表达式 /[ ^ A-Za-z0-9]/g 在字符串中去除非字母和数字，最后将字符串转换为数组。
- 2.转换数组后，利用循环一一比较元素，先比较第一个和最后一个，再比较第二个和倒数二个，依次类推，若中间有不相等则不是回文串，反之，则是回文串。

代码2


   /**
     * @param {string}
     * @return {boolean}
     */
    const isPalindrome = (s) => {
    // 将传入的字符串,统一转化为小写,同时去除非字母和数字,在转换为数组
    const arr = s.toLowerCase().replace(/[^A-Za-z0-9]/g, '').split('');
    let i = 0;
    let j = arr.length - 1;
    // 循环比较元素
    while (i < j) {
        // 从首尾开始, 一一比较元素是否相等
        if (arr[i] === arr[j]) {
        // 若相等,即第二个元素和倒数第二个元素继续比较,依次类推
        i += 1;
        j -= 1;
        } else {
        // 只要有一个相对位置上不相等,既不是回文串
        return false;
        }
    }
    // 是回文串
    return true;
    };