Genom åren har det blivit en klassisk kodintervjufråga att kontrollera om en sträng är en palindrom eller inte. Detta beror på att det handlar om begrepp kring strängmanipulation och jämförelse och till och med loopar beroende på implementeringen. Och frågan är inte lång så att den kan slutföras inom intervjuerna. Den här artikeln innehåller implementering för att kontrollera om en sträng är palindrom i java och python.
Vad är en palindrom?
Enligt synonym.com är definitionen av palindrom "ett ord eller en fras som läser samma bakåt som framåt." I grund och botten betyder det att om du skriver ordet eller frasen i omvänd ordning kommer det att vara exakt samma som när det var framåt. Till exempel är pappa och mamma palindromer och pappa och mamma inte. Ordet "palindrom" kommer från två grekiska rotord, "palin" som betyder igen och "dromos" betyder väg eller riktning. Det myntades av den engelska dramatikern Ben Jonson på 1600-talet.
Lösning
- Det vanligaste och enklaste sättet att lösa frågan är att vända strängen först och sedan jämföra den med den ursprungliga strängen. Detta tillvägagångssätt kommer att vara O (n) i stor-O-notering eftersom strängåterföring är O (n).
- Ett annat sätt skulle vara att börja jämföra tecken från början och slut och fortsätta tills du når mitten. Detta tillvägagångssätt har en tidskomplexitet av O (n / 2) men i stor-O-notering kommer det fortfarande att vara O (n). Men fördelen med det här tillvägagångssättet är att du kan returnera False så snart du stöter på den första oöverensstämmelsen, medan det med det första tillvägagångssättet, eftersom att vända en sträng är det första steget, blir tidskomplexiteten alltid O (n).
Palindrom i Python-implementering
Följande är koden för att kontrollera om en sträng är palindrom i python.
def is_palindrome (s): "" "Returnerar sant om givna argument s är en palindrom annars Falsk" "" påstående (isinstance (s, str)), "Argument s är inte av typ "# Påstå om det givna argumentet är av typ returnera s [:: - 1] == s # Jämför strängens baksida med sig själv om __namn __ == "__ main__": skriv ut (is_palindrome ("pappa")) def is_palindrome (word): "" "Jämför karaktärerna en efter en från början och slutet och returnerar False när den första felparningen inträffar eller annars returnerar True" "i1, i2 = 0, len (ord) -1 # Initiera markörerna medan i2> i1: om ord [i1]! = ord [i2]: # Om tecknen inte stämmer överens, behöver du inte gå vidare returnera Falskt i1 + = 1 i2- = 1 retur Sant om __namn __ == "__ main__ ": skriv ut (is_palindrome (" pappa ")) Palindrom i Java-implementering
Följande är koden för att kontrollera om en sträng är palindrom i Java.
public class Palindrome {public static Boolean isPalindrome (String str) {StringBuilder sb = new StringBuilder (str); // StringBuilder har omvänd metod return sb.reverse (). ToString (). Är lika med (str); // Jämför strängens baksida med sig själv} public static void main (String args []) {Boolean b = isPalindrome ("dad"); System.out.println (b); }}public class Palindrome {public static Boolean isPalindrome (String str) {int i1 = 0; int i2 = str. längd () - 1; medan (i2> i1) {if (str.charAt (i1)! = str.charAt (i2)) {return false; } i1 ++; i2--; } returnera sant; } public static void main (String args []) {Boolean b = isPalindrome ("dad"); System.out.println (b); }} 
