Валидный палиндром

Валидный палиндром - полное решение

Описание задачи

Валидный палиндром - это строка, которая читается одинаково с обоих концов, если учитывать только буквы и цифры (игнорируя спецсимволы и регистр). Это классическая задача на двухпоказательную технику (two-pointers).

Подходы решения

Подход 1: Two-Pointers (оптимальный)

• Используем два указателя с начала и конца
• Пропускаем невалидные символы
• Сравниваем символы без учета регистра
• Time: O(n), Space: O(1)

Подход 2: Фильтрация строки

• Сначала очищаем строку от спецсимволов
• Затем проверяем палиндром
• Time: O(n), Space: O(n)

Реализация (два варианта)

Вариант 1: Two-Pointers (рекомендуется)

package main

import (
    "fmt"
    "unicode"
)

func isPalindrome(s string) bool {
    left := 0
    right := len(s) - 1
    
    for left < right {
        // Пропускаем невалидные символы слева
        for left < right && !isAlphaNumeric(rune(s[left])) {
            left++
        }
        
        // Пропускаем невалидные символы справа
        for left < right && !isAlphaNumeric(rune(s[right])) {
            right--
        }
        
        // Сравниваем буквы без учета регистра
        if toLower(rune(s[left])) != toLower(rune(s[right])) {
            return false
        }
        
        left++
        right--
    }
    
    return true
}

// Проверяет, является ли символ буквой или цифрой
func isAlphaNumeric(r rune) bool {
    return unicode.IsLetter(r) || unicode.IsDigit(r)
}

// Преобразует букву в нижний регистр
func toLower(r rune) rune {
    if r >= A && r <= Z {
        return r + 32
    }
    return r
}

func main() {
    testCases := []struct {
        input    string
        expected bool
    }{
        {"A man, a plan, a canal: Panama", true},
        {"race a car", false},
        {" ", true},
        {"0P", false},
        {"a.", true},
        {".,", true},
    }
    
    for _, tc := range testCases {
        result := isPalindrome(tc.input)
        status := "✓"
        if result != tc.expected {
            status = "✗"
        }
        fmt.Printf("%s Input: %q => %v (expected %v)\\n", status, tc.input, result, tc.expected)
    }
}

Вариант 2: Фильтрация строки

func isPalindromeSimple(s string) bool {
    // Фильтруем строку, оставляя только буквы и цифры
    cleaned := make([]rune, 0)
    
    for _, r := range s {
        if isAlphaNumeric(r) {
            cleaned = append(cleaned, toLower(r))
        }
    }
    
    // Проверяем палиндром
    for i := 0; i < len(cleaned)/2; i++ {
        if cleaned[i] != cleaned[len(cleaned)-1-i] {
            return false
        }
    }
    
    return true
}

Анализ сложности

Two-Pointers:

• Time: O(n) - один проход через строку
• Space: O(1) - используем только два указателя

Фильтрация:

• Time: O(n) - два прохода (фильтрация + проверка)
• Space: O(n) - создаем новый массив символов

Ключевые моменты

1. Два указателя - эффективный способ сравнения начала и конца
2. Пропуск невалидных символов - важный этап обработки
3. Нормализация регистра - использование unicode.IsLetter и простой конвертации
4. Граничные случаи - пустые строки, только спецсимволы, одиночные символы

Граничные случаи

• Пустая строка - true (валидный палиндром)
• Только спецсимволы - true (после фильтрации остается пусто)
• Одиночный символ - true
• Смешанный регистр с цифрами - корректно обрабатывается
• Невалидный палиндром - false