Тестване на палиндроми — част 3

Във втора част на урока намерихме най-добрия начин за премахване на всички символи, освен букви, за да можем да тестваме палиндрома.

В този урок ще разгледаме начин за проверка дали в прав и обратен ред текстът, който тестваме е еднакъв. С други думи — дали е палиндром.

Сравняваме буква по буква, като вземем първата и последната, после втората и предпоследната и т.н.

Вземане на конкретна буква

Взимане на буква от string може да стане чрез функцията substr(). Тази функция би трябвало вече да е позната от урока функции за текст.

Аргументите, които тази функция приема са 3:

1. string-а, от който искаме да “отрежем” парче
   
2. начална позиция
   
3. дължина на отрязъка
   

Последният аргумент не е задължителен, и ако не е зададен ще върне текста до край.

Така че:

substr('some text', 5);

ще върне “text”, защото ще прескочим първите 5 знака (включва се празният интервал) и ще върне текста до края.

Ако имаме:

substr('some text', 0, 1);

това ще върне “s”. Няма да прескочим никакви знаци. Ще започнем от самото начало и ще върнем string с дължина 1 буква.

По този начин можем да вземем първата, втората и т.н. буква от даден текст.

Взимане на букви отзад-напред

Можем да използваме същата функция, за да вземем последната, предпоследната и т.н. буква, със съвсем малка промяна.

substr('some text', -1, 1);

ще върне “t” — последната буква.

Функцията работи така, че ако вторият аргумент, този, който определя колко букви трябва да прескочим, е отрицателно число, ще започнем толкова знака преди края.

Може да си го представите все едно, че текстът е увит около нещо кръгло. Когато от първата буква се върнем 1 назад отиваме на последната. Само, че тази аналогия не е напълно правилна, тъй като:

substr('some text', -2);

ще върне само “xt”. Отново при достигане до края на текста функцията спира и връща резултата. Без да се взима предвид “кръговата” функционалност, която е описано по-горе.

Изцикляне на всички букви от изречението

Значи първа буква (аргумент 0), трябва да сравняваме с -1, втората буква (1), трябва да сравняваме с -2. Хубаво е човек да си разиграе на ум 1-2 примерни цикъла, преди да започне да пише код. Тогава тази разлика в абсолютните стойности (модул) от числата трябва да се вземе предвид.

Освен това трябва да се обмисли и вариантът за последна буква. В единия случай ще е 11, но в другия не можем да имаме -12. Няма 12 букви и не можем да се върнем толкова назад.

В този случай трябва да се направи проверка и да се вземе първата буква с индекс 0.

Значи трябва да сравняваме резултатите от тази функция, викани по подобен начин, толкова пъти колкото букви имаме в първоначалния текст. Тъй като ще извършваме една и съща операция неколкократно най-добре това би било с цикъл. Единственото, което трябва да се уточни е колко пъти ще бъде изпълнен цикъла. Всъщност — вече го казахме — толкова пъти, колкото букви има в текста. А това можем да го разберем с функцията strlen():

# подготваме string за тестване
$test = 'If I Had a Hi-Fi';

# премахваме всички знаци, освен букви
$simplified = preg_replace('/\W/', '', $test);

# по презюнкция текстът е палиндром; в моментът в който установим, че не е ще променим и този флаг
$is_palindrome = true;

# изпълняваме тялото на цикъла толкова пъти, колкото букви има в $simplified
for ($i = 0; $i < strlen($simplified); $i++) {
    $index_b = -($i+1);

    if ($index_b < - (strlen($simplified)) ) {
        $index_b = 0;
    }

    # взимаме първата буква
    $a = substr($simplified, $i, 1);

    # взимаме последната буква
    $b = substr($simplified, $index_b, 1);

    # проверяваме дали първата и последната буква са еднакви
    if ($a != $b) {
        # ако не са -- отбелязваме, че текстът, който тестваме не е палиндром
        $is_palindrome = false;
    }
}

# извеждаме резултата
var_dump($is_palindrome);

Само че това не работи, защото изкарва false накрая.

Главни и малки букви

Защо се получава това? Защото буквите може да са малки и главни и тогава не са еднакви. Това можем да оправим с обикновено strtolower(), след като премахнем излишните знаци. Нищо не пречи да го направим и преди това де.

Оптимизация

Преди да сме разгледали обновения код — нека видим какво още можем да оптимизираме.

Можем да намалим броя на повторенията на цикъла. Ако първата имаме съвпадение до средата — няма нужда да правим повече проверки. Ние реално повтаряме тези, които вече сме направили.

Затова можем условието $i < strlen($simplified) да го променим да е два пъти по-малко.

В този случай отпадат и проверките за $index_b, което също скъсява кода.

Освен това можем да прекратим цикъла още първия път, когато установим, е текстът не е палиндром. Няма нужда да правим повече проверки.

Цикъла може да прекратим преждевременно с ключовата дума break:

$test = 'If I Had a Hi-Fi';

$simplified = preg_replace('/\W/', '', $test);
$simplified = strtolower($simplified);

$is_palindrome = true;

$repetition = strlen($simplified);

# достатъчно е да проверим до средата, тъй като се очаква да е огледално
$repetition = $repetition / 2;

for ($i = 0; $i < $repetition; $i++) {
    $a = substr($simplified, $i, 1);
    $b = substr($simplified, -($i+1), 1);

    # стриктната проверка работи маааалко по-бързо
    if ($a !== $b) {
        $is_palindrome = false;

        # няма нужда да правим повече проверки -- вече е ясно, че не е палиндром
        break;
    }
}

var_dump($is_palindrome);

Въпреки, че направихме няколко оптимизации, като цяло вършим доста работа и тази проверка не е най-добрата, която можем да постигнем.

В следващия урок ще разгледаме друг начин, който не само е по-бърз за изпълнение от компютрите, но и е доста по-кратък (следователно — лесен и за програмистите).