Implementierung eines effizienten Algorithmus zur Ermittlung der Schnittmenge zweier Zeichenketten

Question

Implementieren Sie einen Algorithmus, der zwei Zeichenketten als Eingabe nimmt und die Schnittmenge der beiden zurückgibt, wobei jeder Buchstabe höchstens einmal vorkommt.

Algo: (die verwendete Sprache wird c# sein)

1. Beide Zeichenketten in ein char-Array umwandeln
2. das kleinere Array zu nehmen und eine Hash-Tabelle dafür zu erstellen, wobei der Schlüssel das Zeichen und der Wert 0 ist
3. Nun durchlaufen Sie das andere Array und erhöhen die Anzahl in der Hashtabelle, wenn das Zeichen darin vorhanden ist.
4. Nun werden alle Zeichen für die Hashtabelle entfernt, deren Wert > 0 ist.
5. Dies sind Schnittmengenwerte.

Dies ist eine O(n)-Lösung, die jedoch zusätzlichen Platz, 2 Char-Arrays und eine Hashtabelle benötigt

Fällt euch eine bessere Lösung als diese ein?

Answer 1

Wie wäre es damit ...

var s1 = "aabbccccddd";
var s2 = "aabc";

var ans = s1.Intersect(s2);

Answer 2

Ich habe das nicht getestet, aber hier ist mein Gedanke:

1. Quicksortieren Sie beide Zeichenketten an Ort und Stelle, so dass Sie eine geordnete Folge von Zeichen haben
2. Behalten Sie einen Index in beiden Zeichenfolgen, vergleichen Sie das "nächste" Zeichen aus jeder Zeichenfolge, wählen Sie das erste aus und geben Sie es aus, wobei der Index für diese Zeichenfolge erhöht wird.
3. Fahren Sie fort, bis Sie das Ende einer der Zeichenketten erreicht haben, und ziehen Sie dann einfach eindeutige Werte aus dem Rest der verbleibenden Zeichenkette.

Benötigt keinen zusätzlichen Speicher, sondern nur die beiden ursprünglichen Zeichenketten, zwei Ganzzahlen und eine Ausgabezeichenkette (oder einen StringBuilder). Als zusätzlicher Bonus werden die Ausgabewerte auch noch sortiert!

Teil 2: Das würde ich schreiben (sorry für die Kommentare, bin neu bei stackoverflow):

private static string intersect(string left, string right)
{
  StringBuilder theResult = new StringBuilder();

  string sortedLeft = Program.sort(left);
  string sortedRight = Program.sort(right);

  int leftIndex = 0;
  int rightIndex = 0;

  //  Work though the string with the "first last character".
  if (sortedLeft[sortedLeft.Length - 1] > sortedRight[sortedRight.Length - 1])
  {
    string temp = sortedLeft;
    sortedLeft = sortedRight;
    sortedRight = temp;
  }

  char lastChar = default(char);
  while (leftIndex < sortedLeft.Length)
  {
    char nextChar = (sortedLeft[leftIndex] <= sortedRight[rightIndex]) ? sortedLeft[leftIndex++] : sortedRight[rightIndex++];

    if (lastChar == nextChar) continue;

    theResult.Append(nextChar);
    lastChar = nextChar;
  }

  //  Add the remaining characters from the "right" string
  while (rightIndex < sortedRight.Length)
  {
    char nextChar = sortedRight[rightIndex++];
    if (lastChar == nextChar) continue;

    theResult.Append(nextChar);
    lastChar = nextChar;
  }
  theResult.Append(sortedRight, rightIndex, sortedRight.Length - rightIndex);

  return (theResult.ToString());
}

Ich hoffe, das macht mehr Sinn.

Answer 3

Sie brauchen keine 2 char-Arrays zu verwenden. Der Datentyp System.String hat einen eingebauten Indexer nach Position, der das Zeichen ab dieser Position zurückgibt, so dass Sie einfach eine Schleife von 0 bis (String.Length - 1) durchlaufen können. Wenn Sie mehr an der Geschwindigkeit als an der Optimierung des Speicherplatzes interessiert sind, könnten Sie ein HashSet für eine der Zeichenketten erstellen und dann ein zweites HashSet, das Ihr Endergebnis enthält. Dann wird die zweite Zeichenkette durchlaufen, wobei jedes Zeichen mit dem ersten HashSet verglichen wird, und wenn es vorhanden ist, wird es dem zweiten HashSet hinzugefügt. Am Ende haben Sie bereits ein einziges HashSet mit allen Schnittmengen und ersparen sich das Durchlaufen der Hashtabelle auf der Suche nach Zeichen mit einem Wert ungleich Null.

EDIT: Ich habe dies vor all den Kommentaren zu der Frage eingegeben, ob ich überhaupt keine eingebauten Container verwenden möchte

Answer 4

Ich würde das folgendermaßen machen. Es ist immer noch O(N) und es verwendet keine Hashtabelle, sondern ein int-Array der Länge 26. (idealerweise)

1. Erstellen Sie ein Array mit 26 Ganzzahlen, wobei jedes Element für einen Buchstaben des Alphabets steht. init to 0's.
2. iteriert über die erste Zeichenkette und verringert den Wert um eins, wenn ein Buchstabe gefunden wird.
3. iteriert über die zweite Zeichenkette und nimmt den Absolutwert von dem Index, der einem beliebigen Buchstaben entspricht. (edit: Dank an scwagner in den Kommentaren)
4. gibt alle Buchstaben zurück, die allen Indizes entsprechen, deren Wert größer als 0 ist.

immer noch O(N) und zusätzlicher Platz von nur 26 Ints.

Wenn Sie nicht nur auf Klein- oder Großbuchstaben beschränkt sind, kann sich die Größe des Feldes natürlich ändern.

Answer 5

"wobei jeder Buchstabe höchstens einmal vertreten ist"

Ich nehme an, dass dies bedeutet, dass Sie nur die Schnittpunkte kennen müssen und nicht, wie oft sie vorkommen. Wenn das so ist, können Sie Ihren Algorithmus durch die Verwendung von Ertrag . Anstatt die Zählung zu speichern und die zweite Zeichenkette auf der Suche nach weiteren Übereinstimmungen weiter zu iterieren, können Sie die Schnittmenge gleich hier ermitteln und mit der nächsten möglichen Übereinstimmung der ersten Zeichenkette fortfahren.