Za ta léta se kontrola, zda je řetězec palindromem či nikoli, stala klasickou otázkou kódovacího rozhovoru. Důvodem je, že zahrnuje koncepty kolem manipulace s řetězci a porovnání a dokonce i smyčky v závislosti na implementaci. A otázka není zdlouhavá, takže ji lze dokončit v časových omezeních rozhovoru. Tento článek obsahuje implementaci pro kontrolu, zda je řetězec palindrom v Javě a Pythonu.
Co je palindrom?
Podle synonym.com je definice palindromu „slovo nebo fráze, která zní stejně vzad i vpřed.“ V zásadě to znamená, že pokud napíšete slovo nebo frázi obráceně, bude to přesně stejné, jako když bylo vpřed. Například táta a matka jsou palindromy a otec a matka nejsou. Slovo „palindrom“ pochází ze dvou řeckých kořenových slov, „palin“ znamená znovu a „dromos“ znamená cestu nebo směr. Vytvořil jej anglický dramatik Ben Jonson v 17. století.
Řešení
- Nejběžnějším a nejsnadnějším způsobem, jak vyřešit otázku, je nejprve obrácení řetězce a jeho porovnání s původním řetězcem. Tento přístup bude O (n) v notaci big-O, protože obrácení řetězce je O (n).
- Jiným způsobem by bylo začít porovnávat postavy od začátku a do konce a pokračovat, dokud se nedostanete do středu. Tento přístup má časovou složitost O (n / 2), ale v notaci big-O to bude stále O (n). Výhodou tohoto přístupu však je, že můžete vrátit False, jakmile narazíte na první nesoulad, zatímco s prvním přístupem, protože obrácení řetězce je prvním krokem, bude časová složitost vždy O (n).
Palindrom v implementaci Pythonu
Následuje kód pro kontrolu, zda je řetězec palindrom v pythonu.
def is_palindrome (s): "" "Vrací True, pokud daný argument s je palindrom else False" "" assert (isinstance (s, str)), "Argument s není typu "# Tvrdit, pokud je daný argument typu return s [:: - 1] == s # Porovnat zadní stranu řetězce se sebou, pokud __name __ == "__ main__": print (is_palindrome ("dad")) def is_palindrome (word): "" "Porovná jednotlivé znaky od začátku a na konec a vrátí False, když dojde k první neshodě, nebo vrátí True" "" i1, i2 = 0, len (slovo) -1 # Inicializovat kurzory while i2> i1: if word [i1]! = word [i2]: # Pokud se znaky neshodují, není třeba pokračovat dále return False i1 + = 1 i2- = 1 return True if __name __ == "__ main__ ": print (is_palindrome (" dad ")) Palindrom v implementaci Java
Následuje kód pro kontrolu, zda je řetězec v java palindrom.
veřejná třída Palindrome {public static Boolean isPalindrome (String str) {StringBuilder sb = new StringBuilder (str); // StringBuilder má reverzní metodu return sb.reverse (). ToString (). Equals (str); // Porovnej zadní stranu řetězce} public static void main (String args []) {Boolean b = isPalindrome ("dad"); System.out.println (b); }}veřejná třída Palindrome {public static Boolean isPalindrome (String str) {int i1 = 0; int i2 = str.length () - 1; while (i2> i1) {if (str.charAt (i1)! = str.charAt (i2)) {return false; } i1 ++; i2-; } návrat true; } public static void main (String args []) {Boolean b = isPalindrome ("dad"); System.out.println (b); }} 
