Valid Palindrome

• tags: [palindrome]

Question

• leetcode: Valid Palindrome | LeetCode OJ

• lintcode: (415) Valid Palindrome

  1. Given a string, determine if it is a palindrome,
     2. considering only alphanumeric characters and ignoring cases.
     3. 4. Example
     4. "A man, a plan, a canal: Panama" is a palindrome.
     5. 7. "race a car" is not a palindrome.
     6. Note
     7. Have you consider that the string might be empty?
     8. This is a good question to ask during an interview.
     9. For the purpose of this problem,
     10. we define empty string as valid palindrome.
     11. 14. Challenge
     12. 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
    7.   8.         l, r = 0, len(s) - 1
    9.   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;
    9.   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.         }
    30.   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;
    8.   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.         }
    29.   30.         return true;
    31.     }
    32. }

源碼分析

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

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

複雜度分析

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