Finden Sie die Länge des längsten Teilstrings

Question

Ich sehe Fragen ähnlich wie diese, aber schließlich für verschiedene Programmiersprachen. Ich versuche, dieses kleine Problem zu lösen:

Gegeben eine Zeichenfolge, finden Sie die Länge der längsten Teilzeichenfolge ohne sich wiederholenden Zeichen. Zum Beispiel ist die längste Teilkette ohne sich wiederholende Buchstaben für abcabcbbabc, die die Länge 3 ist. Für bbbbb ist der längste Teilstring b, mit der Länge 1.

Ich habe nicht die anwer es brauchen, aber warum das, was ich bisher in der zweiten Iteration nicht.

1> longest_substring:main("abcabcbb"). 
H: 97, T: "bcabcbb", Sub: [] 
Is 97 in []? false 
H: 98, T: "cabcbb", Sub: 97 
** exception error: no function clause matching string:chr(97,98,1) (string.erl, line 99) 
    in function longest_substring:process/2 (src/leetcode/algorithms/longest_substring.erl, line 28) 
2> 

Dies ist der Quellcode:

-module(longest_substring). 

-export([main/1]). 

-spec main(S :: string()) -> string(). 

%%%================================================================== 
%%% Export 
%%%================================================================== 
main(S) -> process(S, ""). 

%%%================================================================== 
%%% Internal 
%%%================================================================== 
process([], Sub) -> string:len(Sub); 
process([H | T], Sub) -> 
    io:format("H: ~w, T: ~p, Sub: ~p~n", [H, T, Sub]), 
    Found = string:chr(Sub, H), 
    io:format("Is ~w in ~p? ~p~n", [H, Sub, Found =/= 0]), 
    % Don't know how to make this `if` thing better... 
    if 
    Found > 0 -> process(T, H); 
    _ -> process(T, string:concat(Sub, H)) 
    end. 

Answer 1

Sie zwei Orte, wo man Charakter H als String behandeln, sowohl innerhalb der if:

if 
    Found > 0 -> process(T, H); 
    _ -> process(T, string:concat(Sub, H)) 
end. 

Beide Erscheinungen H Hier muss stattdessen [H] stehen, um eine Zeichenfolge aus dem einzelnen Zeichen zu bilden. (Auch Ihre letzte Klausel in den if muss true verwenden, keinen Unterstrich — Sie einen Compiler-Fehler darüber sollten zu bekommen.)

Derzeit Ihre Lösung liefert eine Zahl, keinen String. Es merkt sich auch keine längere Teilzeichenfolge, die früh in der Zeichenfolge angezeigt werden könnte. Um dies zu beheben, müssen Sie die längste Teilkette erinnern, die Sie bisher gesehen haben, was bedeutet, dass Sie einen anderen Akku benötigen:

-module(longest_substring). 
-export([main/1]). 

-spec main(S :: string()) -> string(). 

main(S) -> process(S, {0,[]}, {0,[]}). 

process([], {LL,Last}, {LG,_}) when LL > LG -> Last; 
process([], _, {_,Long}) -> Long; 
process([H | T], {LL,Last}=Sub, {LG,_}=Long) -> 
    case string:rchr(Last, H) of 
     0 -> 
      process(T, {LL+1,string:concat(Last,[H])}, Long); 
     N -> 
      NewLast = {1+LL-N,string:substr(Last,N+1)++[H]}, 
      process(T, NewLast, 
        case LL > LG of 
         true -> 
          Sub; 
         false -> 
          Long 
        end) 
    end. 

Die main/1 Funktion übergibt zwei Akkumulatoren process/3, von denen jede ein Paar von einer Länge ist und eine Liste. Der erste Akkumulator verfolgt den aktuellen Teilstring, und der zweite folgt dem längsten Teilstring, der bisher gesehen wurde.

In der letzten Klausel von process/3 überprüfen wir zuerst, ob H in der aktuellen Teilkette ist; Wenn nicht, fügen wir es dem aktuellen Teilstring hinzu, erhöhen seine Länge um 1 und rufen process/3 erneut mit dem Ende des Strings auf. Wenn H in der aktuellen Teilzeichenfolge gefunden wird, berechnen wir die neue aktuelle Teilzeichenfolge mit dem Rückgabewert string:rchr/2, um den längsten Teil der vorherigen Teilzeichenfolge beizubehalten (die ursprüngliche Lösung tut dies nicht). Wir überprüfen dann, ob die Länge der aktuellen Teilzeichenkette größer als die aktuell längste Teilzeichenkette ist, und wenn dies der Fall ist, machen wir sie zur längsten Teilzeichenkette, oder wenn wir sie nicht wegwerfen und die aktuell längste Teilzeichenkette behalten Schwanz der Schnur. (Beachten Sie, dass wir diese Überprüfung auch für größer oder gleich statt für größer vornehmen könnten. Dies würde bewirken, dass die Funktion die letzte längste Teilzeichenkette und nicht die erste zurückgibt.)

Die ersten beiden Klauseln von process/3 behandeln den Fall, in dem Eingabezeichenfolge wurde vollständig verarbeitet. Sie entscheiden nur, ob die aktuelle Teilkette länger ist als die bisher längste und die längere der beiden zurückgibt. (Die Alternative, einen größeren oder gleichen Vergleich zu verwenden, gilt auch hier.)

Answer 2

zum Spaß, schlage ich Ihnen vor, komplexe Suche zu vermeiden. In dieser Lösung erstelle ich für jedes Element der Liste einen Prozess, der folgendes enthält: das Element selbst, die PID des nächsten Prozesses/Elements in der Liste und die PID des Aufrufers.

Um die Suche zu starten, sende ich jedem Prozess/Element eine leere Liste.

Jedes Mal, wenn ein Prozess/Element eine Liste erhält, prüft es, ob sein gespeichertes Element ein Mitglied der empfangenen Liste ist. Wenn ja, wird die Liste zurück an den Aufrufer gesendet, wenn das Element nicht der Liste vorangestellt wird und die neue Liste an den nächsten Prozess/Element gesendet wird, um die Auswertung fortzusetzen.

Der Aufrufervorgang wartet einfach auf so viele zurückgesandte Nachrichten wie gesendet.

Ich habe eine Stop-Nachricht und einen Sonderfall für das letzte Element der Liste hinzugefügt.

-module (longer). 

-compile([export_all]). 

char_proc(V,Next,Caller) -> 
    receive 
     stop -> ok; 
     Str -> 
      case lists:member(V,Str) of 
       true -> Caller ! Str; 
       false -> send(Next,Caller,[V|Str]) 
      end, 
      char_proc(V,Next,Caller) 
    end. 

send(noproc,Caller,Str) -> Caller ! Str; 
send(Next,_,Str) -> Next ! Str. 

find(Str) -> 
    Me = self(), 
    Pids = tl(lists:reverse(lists:foldl(fun(X,Acc) -> Pid = spawn(?MODULE,char_proc,[X,hd(Acc),Me]), [Pid|Acc] end,[noproc],Str))), 
    [X ! [] || X <- Pids], 
    R = receive_loop(0,[],length(Str)), 
    [X ! stop || X <- Pids], 
    R. 

receive_loop(N,S,0) -> {N,S}; 
receive_loop(N,S,I) -> 
    receive 
     M when length(M) > N -> 
      receive_loop(length(M),M,I-1); 
     _ -> 
      receive_loop(N,S,I-1) 
    end. 

in der Schale getestet:

1> c(longer). 
{ok,longer} 
2> longer:find("abcdad"). 
{4,"abcd"} 
3> longer:find("abcdadtfrseqgepz"). 
{9,"adtfrseqg"} 
4> longer:find("aaaaaaaaaaaa").  
{1,"a"} 
5> longer:find("abcdatfrseqgepz"). 
{11,"bcdatfrseqg"} 
6> 

Hinweis gibt es keine Garantie über Hexenunterkette zurückgegeben werden, wenn es mehrere Lösungen gibt, ist es sehr einfach, den Code zu ändern, um zurückzukehren entweder die erste Teilzeichenfolge oder alle von ihnen.