Sådan løses Palindrome Index Code Challenge

Sådan løses HackerRanks Palindrome Index Code Challenge med JavaScript

Sådan løses HackerRanks Palindrome Index Code Challenge med JavaScript

Problem

Lad os fordele udfordringen i krav:

  • Link til udfordring: HackerRanks Palindrome Index Code Challenge
  • Du modtager en streng, s
  • s er mellem 1 og 100005 inklusive
  • Du har lov til at fjerne et brev
  • Hvis du fjerner et brev, skal du returnere dets indeks
  • Strengen efter at have fjernet brevet vil svare til sig selv baglæns (a.k. palindrome)
  • Hvis ingen streng fjernes, eller der skal fjernes mere end et tegn, skal du returnere -1
// Eksempel
"Ababab"
// Resultat
5
// Årsag, når indeks 5 fjernes
"ababa" = "ababa" det modsatte

Mål

Skriv en funktion eller funktioner, der returnerer indekset for det bogstav, der er fjernet fra streng (er) for at gøre det til en palindrome, og -1 er det ikke muligt, eller er ingen streng fjernet

Dækker vores baser

Sørg for, at vi opfylder kravene:

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005) {
           // fortsæt kode
     }
      
     returneresultat;
}

Vi er også nødt til at medregne, hvis strengen i sig selv vendes ikke behøver nogen tegn fjernet for at gøre det til en palindrome.

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           // fortsæt kode
     }
      
     returneresultat;
}

Forstå problemet

Da jeg første gang forsøgte at løse dette problem, kom jeg med en hurtig løsning og derefter refakturerede ting for at gøre det mere effektivt. HackerRank har en måde til ikke kun at evaluere dig om, hvorvidt eller ikke, dine svar er korrekte, men også hvis din kode kører inden for fristen, eller det giver dig en fejl og afbrud. Jeg går gennem min første iteration og derefter hvordan jeg foretog optimeringer.

Når jeg læste problemet, vidste jeg, at for at sammenligne strengen med dets omvendte jeg, skulle jeg krydse den med en løkke for at gennemgå hvert tegn. I det væsentlige skal du fjerne et tegn ad gangen, sammenligne strengen og dens omvendte og enten returnere løsningen eller fortsætte.

Gennemse karakterer

Vi er bestemt nødt til at bruge en for-loop for at gennemgå tegnene:

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Oprettelse af nye strenge

Derefter skal vi oprette en ny streng med tegnet ved indeks i fjerne, oprette det omvendte og sammenligne strengen. Hvis strengen og dens omvendte er ens, har vi en løsning. Når vi bemærker, at dette er en for loop, kan vi tilføje en vis optimering ved at tilføje en pause til vores loop, når vi først har fundet svaret, ikke nødvendigt at fortsætte med at gå gennem loopen.

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Problemer med vores første løsning

Da jeg kørte testene kom de fleste af de oprindelige mindre værdier tilbage med de rigtige resultater. Problemet var, da s var en længde på 73785 eller mere. Resultaterne kom tilbage med:

Afbrudt på grund af timeout

Forstå problemet igen

For at forstå, hvad der var nødvendigt for at løse dette, er vi nødt til at forstå, hvad er det, vi sammenligner? Vi sammenligner en streng med det omvendte jeg. Vi kan derefter antage, at det resultat, vi forsøger at opnå, er at sikre, at det er en palindrome, eller bare validerer en eksisterende palindrome. Dette giver en forståelse af, at vi kunne antage, at uanset hvad der allerede er en palindrome, og vi bare sørger for, at det opfylder kravene til en palindrome.

Palindrome-krav

Kravene til en palindrome er, at den læser den samme fremad og vendt. Det betyder, at det første bogstav er lig med det sidste bogstav, det andet bogstav er lig med det andet sidste bogstav, og så videre. Med denne forståelse sammenligner vi stort set bare bogstaver for at sikre dig, at de er de samme.

// Eksempel - "acbba"
↓ ↓
a c b b a = same
  ↓ ↓
a c b b a =  ikke det samme

Sammenligning af breve

Genfakturering af vores originale løsning fra for-loop ville så se sådan ud:

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Beslutter hvilket brev der skal fjernes

Når vi først har fundet ud af, at begge bogstaver ikke er ens, er vi nødt til at beslutte, om det er bogstavet i begyndelsen eller brevet i slutningen, der skal fjernes.

// Eksempel med for loop - "acbba"
...
i = 1
  ↓ ↓
a c b b a =  ikke det samme
// Forventet svar skal være i (1)
// Eksempel med for loop - "abbca"
...
i = 1
  ↓ ↓
a b b c a =  ikke det samme
// Det forventede svar skal være 3 eller (længde - 1 - i)

Vi er nødt til at evaluere begge scenarier for at finde vores svar.

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Sammenligning af strengene

Når vi har begge strenge, er vi nødt til at sammenligne dem med deres omvendte version og returnere det respektive resultat. Bemærk, at vi stadig er i for loop, så når vi først har svaret, kan vi bryde det for at springe resten af ​​sammenligningen for for loop.

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Dette begynder allerede at se godt ud, men vi er nødt til at indgå i en anden brugssag.

Hvad med mere end et brev

Hvad med scenariet, at der er mere end et bogstav, der skal udskiftes. Baseret på kravene har vi kun tilladelse til at fjerne et bogstav. Med det kan vi antage, at hvis der kræves mere end et bogstav, skal vi returnere -1. Det er her vi kan tilføje vores sidste ellers til at redegøre for dette.

// Eksempel-scenarie - "acbdbba"
...
i = 1
  ↓ ↓
a c b d b b a =  ikke det samme
// hvis vi fjernede c
"abdbba"! = "abbdba"
// hvis vi fjernede b
"acbdba"! = "abdbca"
// for at det skal være en palindrome, er vi nødt til at fjerne et andet brev
// hvilket er ude af vores krav, og dermed resultat = -1

Vores kode vil derefter indeholde det sidste andet som følgende:

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Optimering af koden endnu mere

Der er to sidste optimeringer, vi kunne foretage.

Optimering af flere pauser

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Optimering til sløjfe

Selvom dette ikke virkelig er nødvendigt på grund af pausen, kunne vi også antage, at vi ikke behøver at krydse hele strengen og kun halvvejs, fordi vi antager, at strengen er den samme fremad og vendt. Vi kan derefter skære for loop-længden i to:

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
           
          for (lad i = 0; i 

Selvom det ikke nødvendigvis er nødvendigt, men det kan hjælpe, hvis vi beslutter at faktorere dette for at fjerne en end en karakter.

Løsning

Den fulde løsning uden kommentarerne:

funktion palindromeIndex (s) {
     lad resultat = -1;
     const slen = s.length;
     
     if (slen> = 1 && slen <= 100005 & s! == s.split (''). reverse (). join ('')) {
          for (lad i = 0; i 

Testtilfælde

Lad os validere koden:

// "a", forventet -1
// "", forventet -1
// "acbdbba", Forventet -1
// "aaab", forventet 3
// "acbba", forventet 1
palindromeIndex ( "a"); // -1 
palindromeIndex ( ""); // -1 
palindromeIndex ( "acbdbba"); // -1 
palindromeIndex ( "AAAB"); // 3 
palindromeIndex ( "acbba"); // 1 

Feedback

Hvis du har nogle tip til, hvordan dette kan forbedres eller diskutere kodning / algoritmer, ville jeg meget gerne tale.

Hvis du fik værdi af dette, skal du dele det på twitter eller andre sociale medieplatforme. Tak igen for at have læst.

Følg mig også på twitter: @mannycoding og instagram på @mannycodes.