Czy da sie sprytniej posortowac stringi z listy ?

0

Robie sobie zadania algorytmiczne - anagramy. Pytanie, jak mam liste stringow i chce je posortowac alfabetycznie ( w sensie nie chce miec posortowanej listy, tylko liste w ktorej elementy sa posortowanymi stringami). To da sie to jakos ladniej/sprytniej zrobic ?

        List<String> listOfStrings = Arrays.asList("siala", "baba", "mak", "nie", "wiedziala", "jak");

        listOfStrings = listOfStrings.stream().map(s -> {
            char[] toSort = s.toCharArray();
            Arrays.sort(toSort);
            s = new String(toSort);
            return s;
        }).collect(Collectors.toList());
1

Hej WhiteLightning, jak najbardziej możesz tak zrobić. Wynikiem będzie lista Stringami gdzie każdy String jest posortowany. Jaka jest treść zadania? Bo samo sortowanie w przypadku sprawdzania czy słowa są anagramami nie jest najlepsze jeśli chodzi o złożoność (nlogn). Da się to zrobić pętlą z O(N).

1

Zmapowałeś sortowanie na listę stringów, co więcej Możesz zrobić, lepszej złożoności nie Uzyskasz: nlog(n).

0

Optymalne rozwiązanie jest O(n*k).

2

Można zrobić sobie letter-count na hashmapie dla każdego słowa, więc dostajesz HashMap<String,Long> i to zrobisz w czasie O(k) per słowo (k to długość słowa), więc O(n*k) dla n słów. Przy czy realnie dla krótkich słów to O(n*k*logk) wiele się nie będzie różnić, ba w praktyce może nawet być szybsze.

1 użytkowników online, w tym zalogowanych: 0, gości: 1