125. Valid Palindrome

INFO

Problem: Valid Palindrome

Pattern: String filtering / two pointers

Valid Palindrome asks whether a string reads the same forward and backward after ignoring punctuation, spaces, and letter casing. The important part is not the word "palindrome" itself; it is the cleanup rule.

There are two common ways to solve it in Swift. The first builds a cleaned string, reverses it, and compares both versions. The second uses two pointers and skips invalid characters while scanning inward. The two-pointer version avoids building a full reversed copy.

Approach 1: Clean And Compare

1. Create an empty string.
2. Append only letters and numbers.
3. Convert letters to lowercase.
4. Compare the cleaned string with its reversed version.

This approach is easy to explain and works well for learning.

Approach 2: Two Pointers

1. Convert the string into an array of characters for indexed access.
2. Start one pointer at the beginning and one at the end.
3. Move the left pointer forward until it reaches a letter or number.
4. Move the right pointer backward until it reaches a letter or number.
5. Compare lowercase values.
6. If any pair differs, return false.
7. If all pairs match, return true.

Swift Notes

Swift Character values provide isLetter, isNumber, and lowercased(), which makes the character checks readable. Converting to an array is useful here because direct integer indexing into String is not available in Swift.

Complexity

• Time complexity: O(n).
• Space complexity: O(n) for the cleaned string or character array.

Edge Cases

• An empty string or a string with only spaces should be valid.
• Case differences should not matter.
• Punctuation should be skipped.

// Solution 1

class Solution1 {
    func isPalindrome(_ s: String) -> Bool {
        var newString = ""
        for c in s {
            if c.isLetter || c.isNumber {
                newString.append(c.lowercased())
            }
        }
        let reversedString: String = String(newString.reversed())
        if newString == reversedString {
            return true
        }
        return false
    }
}

var solution1 = Solution1()

var testcase11 = solution1.isPalindrome("A man, a plan, a canal: Panama")
print(testcase11) // true

var testcase12 = solution1.isPalindrome("race a car")
print(testcase12) // false

var testcase13 = solution1.isPalindrome(" ")
print(testcase13) // true


// Solution 2

class Solution2 {
    func isPalindrome(_ s: String) -> Bool {
        var i = 0
        var j = s.count - 1
        let stringArray = s.map { c in
            return c
        }
        while i <= j {
            let ithCharacter = stringArray[i]
            if !ithCharacter.isLetter && !ithCharacter.isNumber {
                i += 1
                continue
            }
            let jthCharacter = stringArray[j]
            if !jthCharacter.isLetter && !jthCharacter.isNumber {
                j -= 1
                continue
            }
            if ithCharacter.lowercased() != jthCharacter.lowercased() {
                return false
            }
            i += 1
            j -= 1
        }
        return true
    }
}

var solution2 = Solution2()

var testcase21 = solution2.isPalindrome("A man, a plan, a canal: Panama")
print(testcase21) // true

var testcase22 = solution2.isPalindrome("race a car")
print(testcase22) // false

var testcase23 = solution2.isPalindrome(" ")
print(testcase23) // true