Tijekom godina provjeravanje je li žica palindrom ili ne postalo je klasično pitanje za kodiranje. To je zato što uključuje koncepte oko manipulacije nizovima i usporedbe, pa čak i petlje, ovisno o implementaciji. Pitanje nije dugo, pa se može ispuniti u vremenskim ograničenjima intervjua. Ovaj članak uključuje implementaciju za provjeru je li niz palindrom u javi i pythonu.
Što je palindrom?
Prema synonym.com, definicija palindroma je "riječ ili fraza koja se čita unatrag kao i naprijed". U osnovi, to znači da ako riječ ili frazu napišete obrnuto, bit će potpuno isti kao kad je proslijeđen. Na primjer, tata i mama su palindromi, a otac i majka nisu. Riječ "palindrom" dolazi od dvije grčke korijenske riječi, "palin" što opet znači i "dromos" što znači put ili smjer. Smislio ga je engleski dramatičar Ben Jonson u 17. stoljeću.
Riješenje
- Najčešći i najjednostavniji način rješavanja pitanja je preokretanjem niza, a zatim usporedbom s izvornim nizom. Ovaj će pristup biti O (n) u velikom O zapisu, jer je preokret niza O (n).
- Drugi bi način bio da započnete uspoređivati likove od početka i do kraja i nastavite dok ne dođete do sredine. Ovaj pristup ima vremensku složenost O (n / 2), ali u velikim O oznakama i dalje će biti O (n). Ali prednost ovog pristupa je u tome što se False možete vratiti čim naiđete na prvu neusklađenost, dok će kod prvog pristupa, budući da je preokret niza prvi korak, vremenska složenost uvijek biti O (n).
Palindrom u implementaciji Pythona
Slijedi kôd za provjeru je li niz palindrom u pythonu.
def is_palindrome (s): "" "Vraća True ako je zadani argument s palindrom, inače False" "" tvrdi (isinstance (s, str)), "Argument s nije tipa "# Utvrdite je li zadani argument tipa return s [:: - 1] == s # Usporedite naličje niza sa sobom ako je __name __ == "__ main__": print (is_palindrome ("tata")) def is_palindrome (riječ): "" "Uspoređuje znakove jedan po jedan od početka i do kraja i vraća False kada se dogodi prva neusklađenost ili inače vrati True" "" i1, i2 = 0, len (riječ) -1 # Inicijaliziraj kursori dok je i2> i1: ako je riječ [i1]! = riječ [i2]: # Ako se znakovi ne podudaraju, nema potrebe za daljnjim vraćanjem False i1 + = 1 i2- = 1 vrati se True ako __ime __ == "__ main__ ": print (is_palindrome (" tata ")) Palindrom u implementaciji Jave
Slijedi kod za provjeru je li niz palindrom u javi.
javna klasa Palindrome {javni statički logički isPalindrom (niz str) {StringBuilder sb = novi StringBuilder (str); // StringBuilder ima reverznu metodu return sb.reverse (). ToString (). Equals (str); // Usporedite naličje niza sa samim sobom} public static void main (String args []) {Boolean b = isPalindrome ("dad"); System.out.println (b); }}javna klasa Palindrome {javni statički logički isPalindrom (Niz str) {int i1 = 0; int i2 = str.length () - 1; while (i2> i1) {if (str.charAt (i1)! = str.charAt (i2)) {return false; } i1 ++; i2--; } return true; } public static void main (String args []) {Boolean b = isPalindrome ("tata"); System.out.println (b); }} 
