ein Array von Strings gegeben, return true, wenn jede Zeichenfolge miteinander verbunden werden könnten

Question

ein Array von Strings gegeben, return true, wenn jede Zeichenfolge miteinander verbunden werden könnten

8

Sie erhalten ein Array von Strings und geben true zurück, wenn und nur wenn alle Strings in einer Kette verbunden werden können.

Bedingung für Konnektivität ist, wenn das letzte Zeichen einer Zeichenfolge mit dem ersten Zeichen der zweiten Zeichenfolge übereinstimmt, dann können die zwei Zeichenfolgen verbunden werden .

Beispiel: String []arr ={"abc", "cde", "cad" , "def" , "eac"} gibt true zurück, da alle Strings in einer Kette verbunden sein können.

%Vor%

Ein anderes Beispiel: String []arr ={"acb" , "cde", "def", "ead" } gibt Falsch zurück, weil
"cde"->"ead"->"def" die mögliche Kette ist, aber "acb" weggelassen wird.

Hinweis : Es ist nicht notwendig, mit der ersten Zeichenfolge zu beginnen und die Kette zu bilden. Es kann vorkommen, dass Sie keine Kette erhalten, wenn Sie mit der ersten Zeichenfolge beginnen. Sie können eine Kette erhalten, wenn Sie mit einer anderen Zeichenfolge beginnen. Wenn es eine mögliche Kette gibt, sollte Ihre Lösung true zurückgeben.

Wenn im zweiten Beispiel der erste String “fcb” wäre, dann hätte eine mögliche Kette existiert, "cde"->"ead"->"def"->"fcb" also True .

MÖGLICHE LÖSUNG (was ich denke): Betrachte jede Zeichenkette als Diagrammknoten und verbinde die Knoten, wenn die Bedingung erfüllt ist. Sobald das erledigt ist, reduziert sich das Problem auf das Finden,

if there exists a Hamiltonian Cycle in a graph , was NP-vollständiges Problem ist.

Wer schlägt irgendeinen Algorithmus oder andere Lösungen vor?

algorithm string arrays data-structures

roger_that 17.07.2013, 17:13

quelle

3 Antworten

Tags und Links algorithm string arrays data-structures

Django: Verwenden von Annotate, Count und Distinct in einem Queryset MongoDB - Abfrage zwischen einem Zeitbereich von Stunden

score 7 · Answer 1

Sie suchen nicht nach einem Hamilton-Zyklus (dh Begin = Start), sondern nach einem Hamilton-Pfad, der ebenfalls ein NP-vollständiges Problem ist. Ihre Diagramme sind jedoch nicht allgemein, da es nur 26 Buchstaben gibt. Wenn Sie mehr als 26 Buchstaben als Symbol zulassen, entspricht dies tatsächlich dem Hamilton-Pfad.

Hier ist eine Lösung: Sie sollten den umgekehrten Weg denken:

der Scheitel des Graphen sind die 26 Buchstaben.
Es gibt eine Kante zwischen den Buchstaben x und y für jedes Wort, beginnend mit x bis endend mit y

Was Sie also bekommen, ist eigentlich ein Multigraph , da mehrere Wörter mit demselben Buchstaben beginnen und enden können. Dann wird das, was Sie suchen, ein Euler-Pfad genannt: Es ist ein Pfad, der jede Kante genau einmal aufnimmt. Das Finden eines Euler-Pfades ist ein polynomisches Problem ( Ссылка ). Es ist wahrscheinlich eines der ersten Graphenprobleme in der Geschichte.

Jetzt zitiert Wikipedia:

Ein gerichteter Graph hat eine Eulersche Spur genau dann, wenn höchstens eine Ecke (out-degree) - (in-grad) = 1, höchstens eine Ecke (in-grad) hat - (Out-Grad) = 1, jeder andere Eckpunkt hat den gleichen Grad und Grad, und alle seine Eckpunkte mit einem Grad ungleich Null gehören zu einer einzelnen verbundenen Komponente des zugrundeliegenden ungerichteten Graphen.

Dies ist ein weitaus besserer Weg, um zu entscheiden, ob es einen Pfad gibt, als nach einem Hamilton-Pfad zu suchen.

score 0 · Answer 2

ähnliche Frage beantwortete hier: Erkennen, wenn die Matrixmultiplikation möglich ist,

Sie können es als Eulersche Wege-Problem lösen, das viel einfacher als ein Hamilton-Pfad ist.

Anstatt jede Zeichenkette zu einem Knoten im Graphen zu machen, machen Sie jeden Buchstaben zu einem Knoten im Graphen. Fügen Sie eine gerichtete Kante zwischen zwei Buchstaben hinzu, wenn eine Zeichenfolge im ersten Buchstaben beginnt und in der anderen endet. Wenn Sie nun in diesem Diagramm einen Euler-Pfad finden, erhalten Sie die erforderliche Lösung.

score 0 · Answer 3

Nehmen wir an, Sie haben ein Alphabet der Größe 26.

Stellen wir uns Ihre Worte als gerichteten Graphen mit 26 Ecken vor, die allen Buchstaben {a, b, ..., z} entsprechen.

Fügen Sie für jedes Wort, das Sie haben, dem Diagramm eine gerichtete Kante hinzu - vom Buchstaben, der das Wort beginnt, bis zum Buchstaben, der es beendet.

Dann suchst du den Euler-Pfad dieses Graphen - den Pfad, der jede Kante besucht (geht durch jedes deiner Wörter) genau einmal.

Es gibt einen berühmten Satz:

Der gerichtete Graph G auf n Ecken hat einen Euler-Pfad iff. mindestens n-1 Scheitelpunkte haben eingehenden Grad gleich ausgehenden Grad.

Darüber hinaus gibt es Algorithmen zur Konstruktion einer solchen Tour in Polynomialzeit, zum Beispiel den Fleury-Algorithmus.