Valid Palindrome

  • tags: [palindrome]

Question

  1. Given a string, determine if it is a palindrome,
  2. considering only alphanumeric characters and ignoring cases.
  4. Example
  5. "A man, a plan, a canal: Panama" is a palindrome.
  7. "race a car" is not a palindrome.
  8. Note
  9. Have you consider that the string might be empty?
  10. This is a good question to ask during an interview.
  11. For the purpose of this problem,
  12. we define empty string as valid palindrome.
  14. Challenge
  15. O(n) time without extra memory.

題解

字符串的回文判斷問題，由於字符串可隨機訪問，故逐個比較首尾字符是否相等最為便利，即常見的『兩根指針』技法。此題忽略大小寫，並只考慮字母和數字字符。鏈表的回文判斷總結見 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.     /**
  3.      * @param s A string
  4.      * @return Whether the string is a valid palindrome
  5.      */
  6.     public boolean isPalindrome(String s) {
  7.         if (s == null || s.isEmpty()) return true;
  9.         int l = 0, r = s.length() - 1;
  10.         while (l < r) {
  11.             // find left alphanumeric character
  12.             if (!Character.isLetterOrDigit(s.charAt(l))) {
  13.                 l++;
  14.                 continue;
  15.             }
  16.             // find right alphanumeric character
  17.             if (!Character.isLetterOrDigit(s.charAt(r))) {
  18.                 r--;
  19.                 continue;
  20.             }
  21.             // case insensitive compare
  22.             if (Character.toLowerCase(s.charAt(l)) == Character.toLowerCase(s.charAt(r))) {
  23.                 l++;
  24.                 r--;
  25.             } else {
  26.                 return false;
  27.             }
  28.         }
  30.         return true;
  31.     }
  32. }

源碼分析

兩步走：

  1. 找到最左邊和最右邊的第一個合法字元(字母或者字元)
  2. 一致轉換為小寫進行比較

字元的判斷盡量使用語言提供的 API

複雜度分析

兩根指標遍歷一次，時間複雜度 O(n), 空間複雜度 O(1).