(双指针之对撞指针)leetcode125.验证回文串-创新互联

文章目录

• 一、题目
• • 1、题目描述
  • 2、基础框架
  • 3、原题链接
• 二、解题报告
• • 1、思路分析
  • 2、时间复杂度
  • 3、代码详解
• 三、本题小知识

10年积累的成都网站设计、成都网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先做网站设计后付款的网站建设流程，更有越秀免费网站建设让你可以放心的选择与我们合作。一、题目 1、题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：
输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。

示例 2：
输入：s = “race a car”
输出：false
解释：“raceacar” 不是回文串。

示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

2、基础框架 3、原题链接 二、解题报告 1、思路分析

   ( 1 ) (1) (1)判断回文串，首先想到双指针分别从首尾开始，一个往后，一个往前同时遍历，判断字符是否相同。
   ( 2 ) (2) (2)题目中的字符串中还包含了除数字字母之外的符号，要求无视这些符号，我们可以在指针遍历到这些符号时直接跳过。
   ( 3 ) (3) (3)同时题目不考虑大小写，所以除了判断字母是否相等外，如果不相等还要判断是否是对应的大小写字母。

2、时间复杂度

最坏时间复杂度为O(n),空间复杂度为O(1)

3、代码详解

C++

class Solution {public:
    bool isPalindrome(string s) {int l = 0;
        int r = s.length()-1;
        while(lwhile(isTrue(s[l]) == 0 && l< r) {l++;
            }
            while(isTrue(s[r]) == 0 && l< r) {r--;
            }
            if (isTrue(s[l]) != isTrue(s[r])) return false;
            l++;
            r--;
        }
        return true;
    }

    int isTrue (char c) {if (c >= '0' && c<= '9'){return 1 + (c-'0');
        }
        if (c >= 'a' && c<= 'z'){return 11 + (c - 'a');
        }
        if (c >= 'A' && c<= 'Z'){return 11 + (c - 'A');
        }
        return 0;
    }
};

三、本题小知识

1.对撞指针的应用

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

新闻名称：(双指针之对撞指针)leetcode125.验证回文串-创新互联
路径分享：http://bjjierui.cn/article/edgjp.html