[PHP] Jak sprawdzić czy dwa wyrazy są dla siebie anagramami (są permutacją)?

Chcesz wykryć czy jeden wyraz jest anagramem drugiego wyrazu.

W różnego rodzaju grach słownym (typową grą są anagramy) wykorzystuje się algorytm sprawdzający, czy dwa podane wyrazy są dla siebie anagramami. Znacznie łatwiej jest wykryć czy są anagramami niż stworzyć wszystkie ich kombinacje (permutacja).

Anagramy to wyrazy, które mają takie same litery występujące w takiej samej ilości, ale na innych miejscach, np. "alga" jest anagramem wyrazu "gala". Jeżeli liczba liter w wyrazach jest inna lub pojawiają się w nich dodatkowe litery, wyrazy nie są anagramami. Zobacz jak szybko sprawdzić czy dwa wyrazy są dla siebie anagramami.

<?

function czyanagram($w1,$w2) {

for ($i=0;$i<strlen($w1);$i++) {

for ($j=0;$j<strlen($w2);$j++) {

if ($w1[$i]==$w2[$j]) {

$w1[$i]=" ";

$w2[$j]=" ";

break;

}

}

}

if ((trim($w1)<>"")or(trim($w2)<>"")) return 1; else return 0;

}

$wynik = czyanagram("alga","gala");

if ($wynik) echo "wyrazy nie są anagramami";

else echo "wyrazy są anagramami";

?>

Algorytm jest bardzo prosty w działaniu - porównuje literę z pierwszego wyrazu z literami wyrazu drugiego. Pętle gwarantują, że porównanie zostanie wykonane dla wszystkich liter. Jeżeli dwie litery w wyrazie są identyczne, zamieniane są one na spację.

Teraz wystarczy porównać czy oba wyrazy po skasowaniu spacji (za pomocą trim()) mają jakieś znaki. Jeżeli nie, to znaczy, że oba zawierały takie same litery w takiej samej ilości, a więc muszą być dla siebie anagramami. Jeżeli jakieś znaki występują, to znaczy, że nie pojawiły się one w drugim wyrazie i słowa nie są anagramami.

Instrukcja break w pętli gwarantuje nam, że znalezione wyrazy wystąpią tylko raz, w przeciwnym wypadku jedna litera w wyrazie pierwszym mogłaby zostać zamieniona w spacje kilka razy w wyrazie drugim.

---