[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?

[lobopol]

A może rozbicie słowa na poszczególne litery i sprawdzanie czy dana litera występuje w tablicy pula, jeżeli tak to usunąć z puli literę i porównywać następny znak z tablicy slowo, jeżeli jest to tak jak poprzednio, jeżeli niema to przerwać operacje. Można by było jeszcze przed rozpoczęciem posortować obie tablice.

[wookieb]

[PHP] pobierz, plaintext 
function checkWords($word, $chars)
{
    $wordLength = strlen($word);
    $charsLength = strlen($chars);
 
    if($charsLength < $wordLength) return false;
 
    for($i=0; $i<$wordLength; $i++)
    {
        $pos = stripos($chars, $word[$i]);
        if($pos===false) return false;
        $chars[$pos] = '';
    }
    return true;
}
 
[PHP] pobierz, plaintext 

[Zyx]

messmaker -> podane przez Ciebie rozwiązanie jest w istocie najprostsze i najlepsze. Sposób wookieba to klasyczny algorytm brutalny (sprawdź wszystko na wszystkim), podczas gdy wystarczy w obu słowach posortować litery i porównać otrzymane wyniki. Jeśli operujemy na niedużym alfabecie o znanym porządku, sortowanie można znacznie uprościć do tzw. "sortowania przez zliczanie", czyli dokładnie tego samego, co podałeś. Haczyk leży niestety po stronie PHP, a mianowicie braku po pierwsze wbudowanej funkcji sortującej litery w słowie, a po drugie prawdziwych tablic ze stałym czasem dostępu do elementu, co stawia sensowność takiej implementacji pod znakiem zapytania. Jednak są to już ograniczenia technologii, a nie wada pomysłu jako takiego. Kombinowałeś jak najbardziej we właściwym kierunku.

[wookieb]

podczas gdy wystarczy w obu słowach posortować litery i porównać otrzymane wyniki.

A czy to nie wyglądałoby tak samo jak w moim algorytmie?

Haczyk leży niestety po stronie PHP, a mianowicie braku po pierwsze wbudowanej funkcji sortującej litery w słowie,

Nie problem napisac. str_split i sort.

[Zyx]

wookieb -> gdzie Ty u siebie sortowanie widzisz? 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

[wookieb]

Zgodzę się i jak będę miał czas potestuję
Co do kosztowności... znasz język programowania który natywnie sortuje litery w słowie? Przecież dla mnie jest to ten sam sposób realizacji.