Valid Palindrome

Tags: Two Pointers, String, Easy

Question

Problem Statement

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.

题解

字符串的回文判断问题，由于字符串可随机访问，故逐个比较首尾字符是否相等最为便利，即常见的『两根指针』技法。此题忽略大小写，并只考虑字母和数字字符。链表的回文判断总结见 Check if a singly linked list is palindrome.

Python

  1. class Solution:
  2.     # @param {string} s A string
  3.     # @return {boolean} Whether the string is a valid palindrome
  4.     def isPalindrome(self, s):
  5.         if not s:
  6.             return True
  8.         l, r = 0, len(s) - 1
  10.         while l < r:
  11.             # find left alphanumeric character
  12.             if not s[l].isalnum():
  13.                 l += 1
  14.                 continue
  15.             # find right alphanumeric character
  16.             if not s[r].isalnum():
  17.                 r -= 1
  18.                 continue
  19.             # case insensitive compare
  20.             if s[l].lower() == s[r].lower():
  21.                 l += 1
  22.                 r -= 1
  23.             else:
  24.                 return False
  25.         #
  26.         return True

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param s A string
  5.      * @return Whether the string is a valid palindrome
  6.      */
  7.     bool isPalindrome(string& s) {
  8.         if (s.empty()) return true;
  10.         int l = 0, r = s.size() - 1;
  11.         while (l < r) {
  12.             // find left alphanumeric character
  13.             if (!isalnum(s[l])) {
  14.                 ++l;
  15.                 continue;
  16.             }
  17.             // find right alphanumeric character
  18.             if (!isalnum(s[r])) {
  19.                 --r;
  20.                 continue;
  21.             }
  22.             // case insensitive compare
  23.             if (tolower(s[l]) == tolower(s[r])) {
  24.                 ++l;
  25.                 --r;
  26.             } else {
  27.                 return false;
  28.             }
  29.         }
  31.         return true;
  32.     }
  33. };

Java

  1. public class Solution {
  2.     public boolean isPalindrome(String s) {
  3.         if (s == null || s.trim().isEmpty()) {
  4.             return true;
  5.         }
  7.         int l = 0, r = s.length() - 1;
  8.         while (l < r) {
  9.             if(!Character.isLetterOrDigit(s.charAt(l))) {
  10.                 l++;
  11.                 continue;
  12.             }
  13.             if(!Character.isLetterOrDigit(s.charAt(r))) {
  14.                 r--;
  15.                 continue;
  16.             }
  17.             if (Character.toLowerCase(s.charAt(l)) == Character.toLowerCase(s.charAt(r))) {
  18.                 l++;
  19.                 r--;
  20.             } else {
  21.                 return false;
  22.             }
  23.         }
  25.         return true;
  26.     }
  27. }

源码分析

两步走：

  1. 找到最左边和最右边的第一个合法字符(字母或者字符)
  2. 一致转换为小写进行比较

字符的判断尽量使用语言提供的 API, while 循环内部使用 if 而不是 while 可将 l < r 的逻辑移至一处。

复杂度分析

两根指针遍历一次，时间复杂度 O(n), 空间复杂度 O(1).