字符串看到 ”回文“ 尝试双指针
最近在看数据结构和算法，努力总结出道~
TL:DR
上一篇文说过有序的数组，试试用指针法遍历
指针的本质是，记住遍历的进度，从而减少无效遍历的范围。
同理，对于字符串来说，如果是回文，有着天然的对称性，非常适合用指针法缩小遍历范围。
什么是回文
回文：正着读和倒着读都一模一样的字符串。
特点：对称！对称！对称！
判断是不是回文的快速 api 方法：str=>str.split('').reverse().join() === str
非 Api 的朴素方法：左右两个指针，只要相等就往中间移动，遍历完则是回文，否则就不是回文
function isPalindrome(str) { let len = str.length; let L = 0; let R = len - 1; // 指针法基本都是while，遍历的条件是左指针始终在左边 while (L < R) { if (str[L] !== str[R]) { return false; } L++; R--; } return true; }
练习：回文类的字符串题目
网络异常，图片无法展示
|
当然如果不知道对称性的情况，可能会暴力的从第一个字符串开始试着删除，然后判断剩下的是不是回文，方法肯定可行，但没有利用好对称性。
其实这里，和判断是不是回文类似，左右双指针，当不相等的时候，尝试对左指针字符和右指针字符尝试进行“跳过”，看看区间在 [L+1, R] 或 [L, R-1] 的字符串是否回文。
function validPalindrome(str) { const len = str.length; let L = 0; let R = len - 1; // 循环条件加个相等，这样循环后面就是不相等的位置 while (L < R && str[L] === str[R]) { L++; R--; } // 判断特定区间是不是回文 if (isPalindrome(L + 1, R) || isPalindrome(L, R - 1)) { return true; } return false; // 方法稍微改成特定区间 function isPalindrome(L, R) { while (L < R) { if (str[L] !== str[R]) { return false; } L++; R--; } return true; } }
可以看下官方视频
