Ostatnio w pracy, kolega pokazał mi problem programistyczny, który próbował rozwiązać w Pythonie. Miał napisać algorytm, który znajduje najdłuższy ciąg znaków uporządkowanych alfabetycznie w łańcuchu znaków. Czyli na przykład, z łańcucha „abcaxydefkkab” powinno zostać zwrócone „defkk”.
Postanowiłem spróbować rozwiązać ten problem w JavaScripcie.
Na pierwszy rzut oka zadanie nie wydawało się być specjalnie skomplikowane. Postanowiłem wykorzystać fakt, że w JavaScripcie, łańcuchami znaków można operować podobnie jak tablicami. Czyli na przykład kod:
1 2 3 4 |
var s ="kot"; console.log(kot[0]); console.log(kot[1]); console.log(kot[2]); |
Wypisze nam kolejno literki ‚k’, ‚o’ oraz ‚t’.
W moim rozwiązaniu użyłem pętli, która przejdzie przez każdą literkę. Wewnątrz tej pętli działać będzie jeszcze jedna pętla, która od aktualnego miejsca, mierzyć będzie ilość uporządkowanych alfabetycznie literek w dalszej części łańcucha znaków.
Dla łatwiejszego zrozumienia algorytmu, najpierw zapiszmy rozwiązanie w pseudokodzie.
1 2 3 4 5 6 7 8 9 10 |
dla każdej literki w łańcuchu dla każdej literki od aktualnej literki do końca łańcucha Czy Aktualna literka jest w alfabecie przed kolejną? TAK Do wyniku dodajemy aktualna literkę Przesuwamy licznik wewnętrznej pętli NIE Do wyniku dodajemy aktualną literkę (!) kończymy aktualny obieg pętli wewnętrznej Porównujemy aktualny wynik z poprzednim, i jeśli jest większy zastępujemy. Zaczyna się kolejny obieg pętli zewnętrznej |
Szczególnie ważny jest moment aby dodać do wyniku ostatnią literkę ciągu uporządkowanych alfabetycznie znaków. Nawet jeśli kolejna literka nie jest w porządku alfabetycznym, aktualna jest. W pseudo kodzie widzę to wyraźnie, ale w kodzie JavaScriptu już nie do końca 🙂
Przyznam się, że sprawiło mi to pewne kłopoty, zablokowało mnie podczas pisania programu 😛 Pomogłem sobie dopiero kiedy rozrysowaniem całości na kartce 🙂
No dobra, przejdźmy do „mięcha” czyli do kodu:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
var s = 'abcaxyt' function substringChecker(s) { var longestSub = ""; for (var i = 0; i < s.length; i++) { var count = 0; var currSub = ""; while((i+count)<s.length){ var curr = i+count; var next = curr+1; if(s[curr] <= s[next]) { currSub += s[curr]; } else { currSub += s[curr]; break; } count++; } if(currSub.length >= longestSub.length) { longestSub = currSub; } }; return longestSub; } var result = substringChecker(s);; console.log(result); |
Czy jest to jedyne rozwiązanie tego problemu? Na pewno nie 🙂
Czy są bardziej optymalne rozwiązania? Na pewno tak 🙂
Jakie? Szczerze mówiąc, dziś nie przychodzi mi do głowy nic lepszego. Zagnieżdżanie pętli to wysoka złożoność obliczeniowa. Nie wiem jak dałoby się to zrobić liniowo, ale jeśli na to wpadnę to na pewno dam znać!
Przemyślenia na koniec
Naprawdę warto się zastanowić nad problemem zanim usiądziemy do pisania kodu. Spróbujmy najpierw rozwiązać go przy pomocy pseudokodu. Korzystajmy ze wszystkiego co pomoże nam bardziej zrozumieć naturę problemu. Jeżeli, tak jak mi, pomaga Tobie rozrysowanie sobie pomysłu na kartce, to rób to. Nawet jeżeli problem wydaje się być błahy, lepiej dobrze się do niego przygotować, zamiast później tracić czas i nerwy nad niedziałającym kodem 🙂
Jak mam rozumiec < i > w kodzie?
Hej Paweł. Ale stary post wykopałeś. Ma już ponad rok 🙂 Dzięki za zwrócenie uwagi na ten problem. Na początku używałem innego pluginu do oznaczania kodu na stronie. Nie interpretował on niestety znaków specjalnych. A nowy to robi, nie rozpoznaje za to kodów, które wtedy używałem. < i > to kod zamieniany na znaki nierówności. Już poprawiłem zawartość posta.
Można użyć funkcji charCodeAt i fromCharCode by zamiast liter porównywać cyfry a finalnie wyświetlać i tak litery, albo stworzyć pomocniczą tablice z alfabetem do porównania.
Proponowany przez ciebie skrypt nie działa dobrze.
Masz jakiś pomysł na drugą wersje skryptu?
Wyświetla w konsoli axy gdy skompiluje Twój kod.