Palindromy i Anagramy

Większość zadań maturalnych to operowanie na tekście (typu string). "Sprawdź, ile słów w pliku to palindromy" lub "Podaj, czy wyrazy X i Y są anagramami". Omówimy sobie oba zjawiska, krok po kroku.

1. Palindrom

Palindrom to wyraz, który czytany od tyłu brzmi dokładnie tak samo jak od przodu. Przykłady palindromów: kajak, potop, zakaz, oko.

Aby sprawdzić, czy wyraz jest palindromem, musimy porównać jego pierwszą literę z ostatnią, drugą z przedostatnią itd. W Pythonie zadanie jest niesamowicie proste, używając odwracania stringa (tzw. "slicing"). W C++ pętla do połowy wyrazu to pewniak.

Python

def czy_palindrom(slowo):
    # slowo[::-1] zwraca nam odwrócony wyraz
    if slowo == slowo[::-1]:
        return True
    return False

print(czy_palindrom("kajak")) # True

C++

#include <iostream>
#include <string>
using namespace std;

bool czyPalindrom(string slowo) {
    int dlugosc = slowo.length();
    
    // Idziemy tylko do połowy
    for (int i = 0; i < dlugosc / 2; i++) {
        // Porównujemy literę i-tą z literą (ostatnią - i)
        if (slowo[i] != slowo[dlugosc - 1 - i]) {
            return false;
        }
    }
    return true;
}

2. Anagram

Dwa słowa są anagramami, jeśli składają się z dokładnie tych samych liter, ale w różnej kolejności. Najprostszym algorytmem jest posortowanie liter w obu wyrazach alfabetycznie. Po sortowaniu, np. kot zmieni się w k, o, t, a tok też w k, o, t. Jeśli posortowane wyrazy są identyczne – to są to anagramy!

[!TIP] Zawsze przed sortowaniem sprawdź, czy obydwa wyrazy mają tę samą długość! Jeśli długości są różne, to na 100% nie są to anagramy.

Python

def czy_anagram(s1, s2):
    # Szybki check długości
    if len(s1) != len(s2):
        return False
        
    # Funkcja sorted zamienia string na posortowaną listę znaków
    return sorted(s1) == sorted(s2)

print(czy_anagram("kot", "tok")) # True

C++

#include <iostream>
#include <string>
#include <algorithm> // Do sortowania
using namespace std;

bool czyAnagram(string s1, string s2) {
    if (s1.length() != s2.length()) return false;
    
    // Sortujemy oba stringi. Funkcja modyfikuje je "w miejscu"
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    
    if (s1 == s2) return true;
    return false;
}