前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【leetcode系列】125. 验证回文串

【leetcode系列】125. 验证回文串

作者头像
lucifer210
发布2019-08-16 10:37:06
6830
发布2019-08-16 10:37:06
举报
文章被收录于专栏:脑洞前端

题目地址

https://leetcode-cn.com/problems/valid-palindrome/description/

题目描述

代码语言:javascript
复制
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:

输入: "race a car"
输出: false

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这是一道考察回文的题目,而且是最简单的形式,即判断一个字符串是否是回文。

针对这个问题,我们可以使用头尾双指针,

  • 如果两个指针的元素不相同,则直接返回false,
  • 如果两个指针的元素相同,我们同时更新头尾指针,循环。直到头尾指针相遇。

时间复杂度为O(n).

拿“noon”这样一个回文串来说,我们的判断过程是这样的:

拿“abaa”这样一个不是回文的字符串来说,我们的判断过程是这样的:

关键点解析

  • 双指针

代码

  • 语言支持:JS,C++

JavaScript Code:

代码语言:javascript
复制
/*
 * @lc app=leetcode id=125 lang=javascript
 *
 * [125] Valid Palindrome
 */
// 只处理英文字符(题目忽略大小写,我们前面全部转化成了小写, 因此这里我们只判断小写)和数字
function isValid(c) {
  const charCode = c.charCodeAt(0);
  const isDigit =
    charCode >= "0".charCodeAt(0) && charCode <= "9".charCodeAt(0);
  const isChar = charCode >= "a".charCodeAt(0) && charCode <= "z".charCodeAt(0);

  return isDigit || isChar;
}
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  s = s.toLowerCase();
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (!isValid(s[left])) {
      left++;
      continue;
    }
    if (!isValid(s[right])) {
      right--;
      continue;
    }

    if (s[left] === s[right]) {
      left++;
      right--;
    } else {
      break;
    }
  }

  return right <= left;
};

C++ Code:

代码语言:javascript
复制
class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty())
            return true;
        const char* s1 = s.c_str();
        const char* e = s1 + s.length() - 1;
        while (e > s1) {
            if (!isalnum(*s1)) {++s1; continue;}
            if (!isalnum(*e)) {--e; continue;}
            if (tolower(*s1) != tolower(*e)) return false;
            else {--e; ++s1;}
        }
        return true;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 脑洞前端 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目地址
  • 题目描述
  • 思路
  • 关键点解析
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档