JS - palindrom stos

Stos ma wiele zastosowań, ale my nie przywykliśmy do myślenia „stosowego”. Trzeba to poprawić, robiąc jak najwięcej ćwiczeń. Zróbmy palindrom stosem.

Ok, to samo co możemy osiągnąć metodą dwóch wskaźników:

function palindromeStack(str){

    str = str.replace(/\s/g, "").toLowerCase();
    
    let stack = [];

    for(const letter of str)
        stack.push(letter);

    for(const letter of str){
        let lastOne = stack.pop();
        if(letter !== lastOne)
            return false;
    }

    return true;
}

Dla O(n) nie ma specjalnie znaczenia, czy pętla jest jedna czy dwie (nie mówimy o zagnieżdżeniu) czy nawet jest jedna pętla dwa wskaźniki. To jest koniec końców O(n) i tyle.

Natomiast sam algorytm działa tak:

Wrzucamy litery od 1 do ostatniej na stos
Stos ma tę cechę, że co wleci pierwsze zleci ostatnie i co wleci ostatnie zleci pierwsze
Jeszcze raz przechodzimy po literach tym razem zrzucając ze stosu i porównujemy czy się zgadzają ze sobą
Napis do małej i bez spacji bo to nie ma znaczenia w przypadku palindromów

Ok, tak wygląda użycie:

console.log(palindromeStack("Kajak"));
//true
console.log(palindromeStack("anna"));
//true
console.log(palindromeStack("Madam Im Adam"));
//true
console.log(palindromeStack("admin"));
//false

Warto się tutaj uczulić, że zawsze są edge cases. Na przykład możemy chcieć poza spacjami wywalić jeszcze znaki interpunkcyjne (apostrof, przecinek). Koniec końców jednak, algorytm znamy.

JS – palindrom stos