反转字符串

在 JS 中，反转字符串我们直接调相关 API 即可

// 定义被反转的字符串 
const str = 'juejin'  
// 定义反转后的字符串
const res = str.split('').reverse().join('') // 转为数组，反向排序，转为字符串！

console.log(res) // nijeuj

判断一个字符串是否是回文字符串

回文字符串，就是正着读和倒着读都一🐱一样的字符串，比如这样的：wwooww

结合这个定义，我们不难写出一个判定回文字符串的方法：

function isPalindrome(str) {
    // 先反转字符串
    const reversedStr = str.split('').reverse().join('')
    // 判断反转前后是否相等
    return reversedStr === str
}

同时，回文字符串还有另一个特性：如果从中间位置“劈开”，那么两边的两个子串在内容上是完全对称的。因此我们也可以结合对称性来做判断 (谨记这个对称的特性，非常容易用到)

function isPalindrome(str) {
    // 缓存字符串的长度
    const len = str.length
    // 遍历前半部分，判断和后半部分是否对称
    for(let i=0;i<len/2;i++) {
        if(str[i]!==str[len-i-1]) {
            return false
        }
    }
    return true
}

回文字符串的衍生问题

真题描述：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1: 输入: “aba”
输出: True
示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。
注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

普普通通的解法

若字符串本身不回文，则直接遍历整个字符串。遍历到哪个字符就删除哪个字符、同时对删除该字符后的字符串进行是否回文的判断，看看存不存在删掉某个字符后、字符串能够满足回文的这种情况。

function isPalindrome(str) {
    // 缓存字符串的长度
    const len = str.length
    // 遍历前半部分，判断和后半部分是否对称
    for (let i = 0; i < len / 2; i++) {
        if (str[i] !== str[len - i - 1]) {
            return false
        }
    }
    return true
}
function t(str) {
    if (isPalindrome(str)) return true
    for (let i = 0; i < str.length - 1; i++) {
        if (isPalindrome(str.substring(0, i) + str.substring(i + 1, str.length))) {
            return true
        }
    }
    return false
}

这个思路真的实现起来的话，在判题系统眼里其实也是没啥毛病的。但是在面试官看来，就有点问题了——这不是一个高效的解法。
如何判断自己解决回文类问题的解法是否“高效”？其中一个很重要的标准，就是看你对回文字符串的对称特性利用得是否彻底。

双指针解法

字符串题干中若有“回文”关键字，那么做题时脑海中一定要冒出两个关键字——对称性 和 双指针。这两个工具一起上，足以解决大部分的回文字符串衍生问题。

回到这道题上来，我们首先是初始化两个指针，一个指向字符串头部，另一个指向尾部

如果两个指针所指的字符恰好相等，那么这两个字符就符合了回文字符串对对称性的要求，跳过它们往下走即可。如果两个指针所指的字符串不等，比如这样：

那么就意味着不对称发生了，意味着这是一个可以“删掉试试看”的操作点。
我们可以分别对左指针字符和右指针字符尝试进行“跳过”，看看区间在 $[left+1, right] 或 [left, right-1]$ 的字符串是否回文。

如果是的话，那么就意味着如果删掉被“跳过”那个字符，整个字符串都将回文：

llet str = "acbdba"
function PalindromeString(str: string): boolean {
    let l = 0
    let r = str.length - 1;
    while (l < r && str[l] === str[r]) {
        l += 1;
        r -= 1
    }
    if (isPalindrome(l, r - 1)) {
        return true
    }
    if (isPalindrome(l + 1, r)) {
        return true
    }

    // 工具方法，用于判断字符串是否回文
    function isPalindrome(st: number, ed: number) {
        while (st < ed) {
            if (str[st] !== str[ed]) {
                return false
            }
            st++
            ed--
        }
        return true
    }
    // 默认返回 false
    return false
}

console.log(PalindromeString(str)); //true