Funkcja sprawdzająca czy wyraz jest isogramem sprawdza zgodność tylko pierwszej litery z drugą

Question

Witam, chciałbym napisać funkcje która sprawdza czy dany wyraz jest isogramem. To znaczy czy litery w nim nie powtarzają się.

Problem polega na tym, że funkcja porównuje tylko dwie pierwsze litery w słowie więc w przypadku "aba" funkcja zwraca wartość "true" co oznaczałoby że wyraz ten jest isogramem, a nim nie jest ze względu na powtarzającą się literkę "a".

#include <iostream>

bool isogram_czy_nie(std::string str) {
    int reason = 0;
    for(int i = 0; i<=str.length(); i++){
        char b = str[i];
        for (int j = 1; j <= str.length(); j++){
          if (b == str[j]){
          reason += 1;
        }
        else{
        reason += 0;
        }
        if (reason > 0){
            return 0;
        }
        else{
            return 1;
        }
      }
    }
}

int main(){
    std::string str;
    std::cin>>str;
    std::cout<< isogram_czy_nie(str);
}

 

Answer 1

Tym sposobem nie wykonasz tego zadania.

Proste podejście to:

1. Posortowanie liter i sprawdzenie czy 2 obok nie są takie same.

2. Przetworzenie std::string na std::unordered_set i sprawdzenie czy oba kontenery zawierają tę samą ilość elementów.

3. inne (dość egzotyczne i przy wstępnych założeniach).

Najprościej, zrób to 1 sposobem.

Comments

Faktycznie, uczę się c++ od tygodnia i nie wpadło mi do głowy, że można litery po prostu posortować. Dziękuje za odpowiedź.

---

Witam, pytanie odnoszące się do tego problemu. Czy rozwiązanie go za pomocą std::map jest w miarę rozsądnym założeniem, czy to za gruba armata?

---

Przy std::map ponosisz koszt zbędnego sortowania wg. klucza. Jeśli coś z rodziny map to std::unordered_map. Będziesz wtedy gromadził ilość wystąpień litery. Następnie sprawdzisz czy jakiekolwiek licznik nie ma wartości większej niż 1.

Klasa alg. dla dodania do std::map to O(log(n)): https://en.cppreference.com/w/cpp/container/map/insert

..a dla wyszukania O(log(n)) (ogólnie: https://en.cppreference.com/w/cpp/container/map/find )

Klasa alg. dla dodania do std::unordered_map to O(n): https://en.cppreference.com/w/cpp/container/unordered_map/insert

.. a dla wyszukania O(1) (ogólnie: https://en.cppreference.com/w/cpp/container/unordered_map/find )

Jeszcze lepszym rozwiązaniem będzie bazowanie na std::set. Jego metoda insert(...) zwraca parę iterator i bool gdzie bool przechowuje true jeśli udało się dodać dane a false jeśli już były :) Stąd rozwiązanie będzie w klasie O(log(n)). Ale zbędne będzie przeglądanie po, odwracanie logiki na pesymistyczną (żeby szybciej znaleźć) czy analizowanie liczników.

Osobiście w rzeczywistym projekcie, nie wiedząc jak duże będą dane, użył bym set. Tu jednak autor pytania (zapewne - co założyłem), ma zabronione użycie czegoś z <algorithm> :)