Nie rozumiem co mam zrobić w tym zadaniu i jak się za to zabrać. Dlaczego "aabbabcccba" ma dawać 28?
0
0
ms_ napisał(a):
Nie rozumiem co mam zrobić w tym zadaniu i jak się za to zabrać. Dlaczego "aabbabcccba" ma dawać 28?
Kluczem tutaj jest which has to count how many balanced subwords exist in the input word
Czyli np dla wyrazu "dad", to byłoby 5, bo w "dad" zawierają się "d", "a", "d", "da" oraz "ad", które są balanced.
Swoją drogą, to to jest bardzo durne zadanie. Nawet jak je zrobisz, to za milion lat nie będziesz musiał użyć tego algorytmu w pracy.
0
To wynika z kombinacji. W skrócie z słowa "aabbabcccba" możesz ułożyć:
"a" - cztery razy
"b" - cztery razy
"c" - trzy razy
"aa", "abbabccc", "ab", "bb", "aabb", "ba", "abba", "ab", "aabbab", "abc", "bc", "cc", "ccc", "cc", "cb", "ba", "cba" - razem 17
@Riddle: nikt nie powiedział, że podane słowo będzie zbalansowane
0
Ok, czyli najlepiej by było utworzyć wszystkie możliwe słowa ze słowa, które wprowadził użytkownik, a następnie zapisać wszystkie do jednej ArrayListy. Następnie sprawdzić każde po kolei czy jest balanced czy też nie. Tylko jak napisać algorytm, który by te wszystkie możliwe kombinacje słów utworzył?
0
ms_ napisał(a):
Ok, czyli najlepiej by było utworzyć wszystkie możliwe słowa ze słowa, które wprowadził użytkownik, a następnie zapisać wszystkie do jednej ArrayListy. Następnie sprawdzić każde po kolei czy jest balanced czy też nie. Tylko jak napisać algorytm, który by te wszystkie możliwe kombinacje słów utworzył?
No nie najlepiej wcale, bo musiałbyś je trzymać w pamięci wszystkie. Już lepiej zrobić iterator, którym można po nich przejechać i od razu zapomnieć.
Co do kombinacji, to jeśli nie przeszkadza Ci O(n2), to najpierw wygeneruj wszystkie dwu-literowe kombinacje, potem wszystkie trzy-literowe, potem wszystkie cztero-literowe, etc. kończąc na "tyłu-literowych jaka jest długość słowa początkowego - 1"
0
Jeśli dobrze rozumiem, albo nie zrozumiałem do końca zadania, musisz zrobić przejście po grafie, najłatwiej policzyć kombinacje, wszystkie dla jednego poziomu, dwóch poziomów i tak do n-1 znaków z podanego wyrazu.
Dla przykładu dla trzech przejście grafu wygląda na tablicach tak.
[a,b,c] -> [b, c] -> [c] co daje abc i tak pętlą for możesz sobie przechodzić usuwać wybrany element robić kopię tablicy, chyba że z powtórzeniami, to nic nie usuwasz, bo cały czas array wygląda tak samo.
Najprościej możesz powtórzyć tą operację rekurencyjnie, bo ilość wystąpień pętli może się zmieniać.
Potem każde wystąpienie danego znaku zliczasz Counterem, czyli jakimś słownikiem, mapą <char, int>, no i jeśli każda litera wystąpiła równą ilość to tam spełnia warunek.
No i te casy testu obsługujesz.
0
Programowanie dynamiczne, zobacz sobie problem optymalnego mnożenia macierzy: https://edu.pjwstk.edu.pl/wyklady/asd/scb/asd14/main14_p2.html