daily leetcode - valid-palindrome - !

题目地址

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

题目描述

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

思路

验证回文字符串是比较常见的问题,所谓回文,就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。但是这里,加入了空格和非字母数字的字符,增加了些难度,但其实原理还是很简单:只需要建立两个指针,left和right, 分别从字符的开头和结尾处开始遍历整个字符串,如果遇到非字母数字的字符就跳过,继续往下找,直到找到下一个字母数字或者结束遍历,如果遇到大写字母,就将其转为小写。等左右指针都找到字母数字时,比较这两个字符,若相等,则继续比较下面两个分别找到的字母数字,若不相等,直接返回false.

时间复杂度为O(n), 代码如下:

解法一:

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1 ;
        while (left < right) {
            if (!isAlphaNum(s[left])) ++left;
            else if (!isAlphaNum(s[right])) --right;
            else if ((s[left] + 32 - 'a') %32 != (s[right] + 32 - 'a') % 32) return false;
            else {
                ++left; --right;
            }
        }
        return true;
    }
    bool isAlphaNum(char &ch) {
        if (ch >= 'a' && ch <= 'z') return true;
        if (ch >= 'A' && ch <= 'Z') return true;
        if (ch >= '0' && ch <= '9') return true;
        return false;
    }
};

我们也可以用系统自带的判断是否是数母字符的判断函数isalnum,参见代码如下;

解法二:

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1 ;
        while (left < right) {
            if (!isalnum(s[left])) ++left;
            else if (!isalnum(s[right])) --right;
            else if ((s[left] + 32 - 'a') %32 != (s[right] + 32 - 'a') % 32) return false;
            else {
                ++left; --right;
            }
        }
        return true;
    }
};

对于该问题的扩展,还有利用Manacher算法来求解最长回文字符串问题,参见我的另一篇博文Manacher's Algorithm 马拉车算法

思路2

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

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

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

时间复杂度为O(n).

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

125.valid-palindrome-1

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

125.valid-palindrome-2

关键点解析

  • 双指针

代码

  • 语言支持:JS,C++,Python

JavaScript Code:


/*
 * @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:

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

Python Code:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():
                left += 1
                continue
            if not s[right].isalnum():
                right -= 1
                continue
            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                break
        return right <= left

    def isPalindrome2(self, s: str) -> bool:
        """
        使用语言特性进行求解
        """
        s = ''.join(i for i in s if i.isalnum()).lower()
        return s == s[::-1]

本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - valid-palindrome - !
文章作者: lonuslan
文章链接: https://louislan.com/articles/2020/07/07/1594092217591.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LouisLan
    评论
    0 评论
avatar

取消