題目網址：https://leetcode.cn/problems/valid-palindrome/

題意：給一 string s, 將其大寫轉換成小寫、並移除非字母和數字的 char, 返回轉換後是否為迴文。

Solution：

想法：利用 Two pointers, 若當前的 char 不為數字 or 字母則跳過, 直到 left、right 相會。判斷式為 left < right 即可, 因為 left == right 時 s[left]、s[right] 必相等, 因此不用判斷

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            // 注意：這裡更新時還是要保持 left < right
            while (left < right && !isalnum(s[left])) {
                left++;
            }

            while (left < right && !isalnum(s[right])) {
                right--;
            }

            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }

            // update ptr
            left++;
            right--;
        }
        return true;
    }
};
  • time：$O(n)$ ➔ while loop 遍歷 s
  • space：$O(1)$ ➔ 只需常數空間