Jak zjistit, zda je řetězec palindrome v Javě a Pythonu

Kontrola, zda je řetězec palindrome, je klasickým úkolem v programovacích pohovorech. Vyžaduje manipulaci s řetězci, porovnávání a případně cykly, přičemž se dá vyřešit během několika minut.

Co je palindrome?

Podle slovníku je palindrome „slovo nebo fráze, která se čte stejně zleva doprava i zprava doleva“. Jinými slovy, po obrácení řetězce získáme přesně stejný text. Příklady: dad, mom. Naopak father a mother palindrome nejsou. Název pochází z řeckých kořenů palin (znovu) a dromos (cesta) a poprvé jej použil Ben Jonson v 17. století.

Řešení

• Nejjednodušší metoda: převrátit řetězec a porovnat ho s originálem. Tato operace má časovou složitost O(n), kde n je délka řetězce.
• Alternativní metoda: porovnávat znaky od začátku a konce směrem ke středu. V nejhorším případě také O(n), ale umožňuje okamžitě vrátit false při první neshodě, což může u dlouhých řetězců ušetřit čas.

Implementace v Pythonu

Příklad jednoduchého kódu:

def je_palindrome(s: str) -> bool:
    s = s.replace(" ", "").lower()
    return s == s[::-1]

Implementace v Javě

Příklad jednoduchého kódu:

public static boolean jePalindrome(String s) {
    s = s.replaceAll(" ", "").toLowerCase();
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return false;
        i++; j--;
    }
    return true;
}

Tip pro interview

• Ujistěte se, zda má být řešení citlivé na velikost písmen. Pokud ano, řetězec Dad není palindrome, protože D ≠ d.