Question

Today problem is 125_Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward.

Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = “A man, a plan, a canal: Panama”

Output: true Explanation: “amanaplanacanalpanama” is a palindrome.

Example 2:

Input: s = “race a car”

Output: false Explanation: “raceacar” is not a palindrome.

Example 3:

Input: s = ” ”

Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

My approach

  1. filter non alphauneric characters.
  2. reverse string, then compare to original.
class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let trimmedStr = s.lowercased().filter { $0.isNumber || $0 >= "a" && $0 <= "z" }
        return trimmedStr == trimmedStr.reversed()
    }
}

My mistakes ✅

  1. binary operator '==' cannot be applied to operands of type 'String' and '[String.Element]' (aka 'Array<Character>')

There is an error in return trimmedStr == trimmedStr.reversed()

The issue occurs because trimmedStr.reversed() returns a ReversedCollection<String>(which behaves like an array), while trimmedStris a String. Swift cannot directly compare these different types.

So, I fixed this code to return trimmedStr == String(trimmedStr).reversed() (convert reversed back to string)

Solution

Filter + Reverse

class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let cleaned = s.lowercased().filter { $0.isLetter || $0.isNumber }
        return cleaned == String(cleaned.reversed())
    }
}

Time-Complexity: O(n) where n is the length of the string Space-Complexity: O(n) for the filtered string

Two-pointers

class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let s = Array(s.lowercased().filter { $0.isLetter || $0.isNumber })
        var left = 0
        var right = s.count - 1

        while left <= right {
            if s[left] != s[right] { return false }
            left += 1
            right -= 1
        }
        return true
    }
}

Reference

ReetCode Solution