Check a string is a palindrome, ignoring case and non-letters
Implement isPalindrome(s) returning true if s reads the same forwards and backwards. Requirements: ignore letter case and skip every non-alphanumeric character (spaces, punctuation). Handle multi-byte UTF-8 correctly (operate on runes, not raw bytes). O(n) time.
func isPalindrome(s string) bool {
// your code here
return false
}Write the implementation.
Lower-case the string and convert to []rune, then two pointers walk inward: skip non-letter/digit runes via unicode.IsLetter/IsDigit, compare r[i] != r[j] → false, and step both. If they cross, it is a palindrome. O(n) time, O(n) space for the rune slice.
- ✗Comparing bytes via
s[i]instead of runes, mishandling multi-byte input - ✗Filtering only letters and dropping digits that should count
- ✗Assuming string
==ignores case and punctuation
- →Why does the byte-index approach fail on a string with multi-byte runes?
- →How would you do it in O(1) extra space without the
[]runeconversion?
Task
Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.
func isPalindrome(s string) bool {
r := []rune(strings.ToLower(s))
i, j := 0, len(r)-1
for i < j {
for i < j && !unicode.IsLetter(r[i]) && !unicode.IsDigit(r[i]) {
i++
}
for i < j && !unicode.IsLetter(r[j]) && !unicode.IsDigit(r[j]) {
j--
}
if r[i] != r[j] {
return false
}
i, j = i+1, j-1
}
return true
}How it works
strings.ToLower drops the case, []rune gives correct handling of multi-byte characters. Two pointers i and j walk inward:
- the inner loops skip anything that is not a letter or digit (
unicode.IsLetter/IsDigit), so spaces and punctuation are ignored; - if the significant characters at the ends differ (
r[i] != r[j]), it is not a palindrome; - otherwise step both pointers inward.
When the pointers cross with no mismatch, the string is a palindrome. O(n) time, O(n) space for the rune slice.
⚠️ Tests the two-pointer technique plus rune handling and input sanitization.
