Problem
A subsequence is formed by deleting zero or more elements while preserving the order of the remaining elements. Find the longest length shared by two arrays. Matching elements need not be adjacent. Return only the length, since several equally long subsequences may exist.
Implement longest_common_subsequence_length(first, second).
Input
first: The first sequence.
second: The second sequence.
Output
Return the maximum common subsequence length. If either array is empty, return 0.
Einschränkungen
Each array has 0…1,000 integers between −1,000,000,000 and 1,000,000,000. Duplicates are allowed.
Beispiele
Eingabe:
first = [1, 3, 2, 4]
second = [3, 1, 2, 4]
Erwartete Ausgabe:
expected = 3Eingabe:
std::vector<long long> first = {1, 3, 2, 4};
std::vector<long long> second = {3, 1, 2, 4};
Erwartete Ausgabe:
long long expected = 3;Eingabe:
long[] first = new long[] {1, 3, 2, 4};
long[] second = new long[] {3, 1, 2, 4};
Erwartete Ausgabe:
long expected = 3;Erläuterung
Both contain [1, 2, 4] in that order, after deleting one value. The original arrays differ, so a length-four match is impossible.
Eingabe:
first = [1, 2]
second = [3, 4]
Erwartete Ausgabe:
expected = 0Eingabe:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Erwartete Ausgabe:
long expected = 0;Erläuterung
The arrays have no shared value, so their only common subsequence is empty.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Hier zählt die Reihenfolge, nicht die Nachbarschaft, also sind Auslassungen wichtiger als direkte Ausrichtung.
Hinweis 2
Nutze Dynamic Programming, wobei jeder Zustand Präfixe der beiden Arrays vergleicht.
Hinweis 3
Wenn Elemente unterschiedlich sind, nimm das bessere Ergebnis, indem du eines aus einer der beiden Sequenzen entfernst; wiederholte Werte können viele gültige Matches erzeugen.
Erwartete Komplexität
Zeit O(nm), zusätzlicher Speicher O(min(n, m))
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.