目 录CONTENT

文章目录

强大的双指针法-回文字符串

Hello!你好!我是村望~!
2022-08-15 / 0 评论 / 0 点赞 / 205 阅读 / 1,135 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

反转字符串

在 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
}

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

双指针解法

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

image-1660548925967

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

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

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

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
0

评论区