[PHP]Sprawdzenie, czy z zestawu liter można ułożyć podane słowo Opcje

[messmaker]

Jak wyżej, mam dane:

[PHP] pobierz, plaintext 
$slowo="owsianka";
$pula ="SIANKAOW";
[PHP] pobierz, plaintext 

Da się z nich ułożyć słowo. z kolei w przypadku:

[PHP] pobierz, plaintext 
$slowo="owsianka";
$pula ="SIANKOW";
[PHP] pobierz, plaintext 

Już się nie da (brakuje drugiego A). Głowię się i głowię, najlepsze co do tej pory wymyśliłem to:

Zliczenie do jednej tablicy ilości wszystkich rodzajów liter w słowie i do drugiej tablicy rodzajów liter w puli. Następnie porównałbym kolejne rodzaje i otrzymał oczekiwaną informację. W teorii powinno działać, jednak coś mi mówi, że da się to zrobić łatwiej. Jak?

[Zyx]

wookieb -> gdzie Ty u siebie sortowanie widzisz? (IMG:style_emoticons/default/smile.gif) Podany przez Ciebie kod bierze literę z pierwszego słowa, a później skanuje w najgorszym przypadku całe drugie słowo, by sprawdzić czy ona tam jest. To nie ma nic wspólnego z sortowaniem. Zapis w pseudokodzie:

Kod

n = długość(s1); // zakładamy, że s1 i s2 są równej długości
for(i = 0; i < n; i++)
{
   znalazlem = false;
   for(j = 0; j < n; j++)
   {
      if(s1[i] == s2[j])
      {
          znalazlem = true;
          break;
      }
   }
   if(!znalazlem)
   {
      błąd();
   }
}
ok();

W najgorszym przypadku dla słów długości n algorytm wykona n^2 iteracji.

Teraz sposób przez zliczanie:

Kod

slownik1 = inicjuj('a' do 'z' na 0);
slownik2 = inicjuj('a' do 'z' na 0);
n = długość(s1);
for(i = 0; i < n; i++)
{
   slownik1[s1[i]]++;
   slownik2[s2[i]]++;
}
for(i = 'a'; i < 'z'; i++)
{
   if(slownik1[i] != slownik2[i])
   {
      błąd();
   }
}
ok();

Ilość iteracji: n + stały czas na zainicjowanie i sprawdzenie słownika, jeśli znamy jego rozmiary. Ewentualnie można nawet z jednym słownikiem - pierwsze słowo dodaje, drugie odejmuje ilość wystąpień. Jeśli litery w słowach są identyczne, na końcu ilości wystąpień każdej litery będą równe 0.

Ad. 2 -> wiem, że nie problem napisać, ale w PHP to się trochę mija z celem właśnie z powodu, który w cytacie pominąłeś, czyli kosztowność tych operacji.

Ten post edytował Zyx 23.03.2010, 22:23:56