验证回文字符串 Ⅱ #35

Activity

1. CodeRookie262

   added

   算法

   on Feb 2, 2021
2. CodeRookie262 commented on Feb 3, 2021

   

   CodeRookie262

   on Feb 3, 2021

   Last edited by CodeRookie262

   OwnerAuthor

   More actions

   var validPalindrome = function (s) {
       let i = 0,
           l = s.length - 1;
       // 双指针遍历字符串
       while (i < l) {
           // 如果遇到差异则分别将左右指针+1，-1，判断接下来的字符串是否是回文
           if (s[i] !== s[l]) {
               return isPalindrome(s, i + 1, l) || isPalindrome(s, i, l - 1)
           }
           i++;
           l--;
       }
   
       return true;
   };
   
   
   // 判断是否是回文字符串
   const isPalindrome = (s, start, end) => {
       while (start < end) {
           if (s[start] !== s[end]) return false;
           start++;
           end--;
       }
       return true;
   }

   🚀React with 🚀1Reacted by yokura μ
3. yokuray commented on Feb 3, 2021

   

   yokuray

   on Feb 3, 2021

   Last edited by yokuray

   More actions

   实现不错，这种题普遍的思想是从两侧开始逐渐往中间收窄区间，难出其右。独立出一个方法专门用于判断回文，减少了代码冗余。利用高低位指针作为循环的继续条件，还减少了中位变量。👍

   这道题很巧妙，相较于单纯的判断是否回文，加上了“可以删除一个元素”的条件后，情况变得复杂。我一开始在遇到不相等的元素时只计算：

   1. 低位向前看一位是否与高位相等
   2. 高位向前看一位是否与低位相等

   没将二者结合起来，结果遇到：

   aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga

   这个流氓直接给我返回了false(ˉ▽ˉ；)...

   var validPalindrome = function (s) {
       if (!s) return false;
   
       for (let lstIdx = s.length - 1, i = 0; i < lstIdx; i++, lstIdx--) {
   
           // 遇到不等的情况，从不等位开始，计算剩余字串
           if (s.charAt(i) !== s.charAt(lstIdx)) {
               // 可以删除一个元素，那么分别计算：
               // 1. 低位向前看一位（+1），是否与高位相等
               // 2. 高位向前看一位（-1），是否与低位相等
               // 只要有一个结果计算是回文，那么就是回文。
               // 因为存在类似：aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga
               // 这样的“流氓”，
               // cupuu
               // uupucu
               // 低位向前一位相等，容易让我们误以为是回文，但是下个元素直接打脸，而高位向前结果是回文，
               // 因此高低位向前均要同时考虑。
               let r1 = true, r2 = true;
               // 低位元素略过一位，计算剩余是否回文
               for (let l1 = i + 1, h1 = lstIdx; l1 < h1; l1++, h1--) {
                   // 已经略过一个元素了，再不相等结果为false并跳出
                   if (s.charAt(l1) !== s.charAt(h1)) r1 = false; break;
               }
   
               // 高位元素略过一位，计算剩余是否回文
               for (let l2 = i, h2 = lstIdx - 1; l2 < h2; l2++, h2--) {
                   // 已经略过一个元素了，再不相等结果为false并跳出
                   if (s.charAt(l2) !== s.charAt(h2)) r2 = false; break;
               }
   
               return r1 || r2;
           }
       }
   
       return true; // 不删除元素，本身是回文
   };

   👍React with 👍1Reacted by CodeRookie262
4. CodeRookie262 commented on Feb 3, 2021

   

   CodeRookie262

   on Feb 3, 2021

   OwnerAuthor

   More actions

   嗯嗯，这道题难点在非回文字符串如何进行取舍处理 @Mirai39