Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Short Tandem Repeats in der DNA zählen

Finde für jede kurze Tandemwiederholung die längste Folge direkt aufeinanderfolgender Kopien in einer DNA-Sequenz.

Das lernst du

  • Einen Teilstring mit einem Muster vergleichen
  • Direkt aufeinanderfolgende Kopien ab einer Position zählen
  • Für jedes Muster den besten Wert behalten

Problem

Rechtsmedizinische Labore vergleichen Menschen anhand von Short Tandem Repeats (STRs): kurzen DNA-Abschnitten wie AGAT, die viele Male direkt hintereinander vorkommen. Für jeden Abschnitt notiert das Labor die längste Folge aufeinanderfolgender Kopien irgendwo in der Sequenz. In TTAGATAGATAGATCAGATAGAT kommt AGAT am Anfang dreimal hintereinander vor und später zweimal, sein Wert ist also 3.

Implementiere dna_str_count(sequence, repeats).

Eingabe

sequence: Die DNA-Sequenz aus den Buchstaben A, C, G und T.

repeats: Die STR-Abschnitte, die gemessen werden sollen.

Ausgabe

Gib pro Abschnitt einen Wert zurück, in derselben Reihenfolge wie in repeats: die größte Zahl von Kopien, die direkt hintereinander vorkommen. Ein Abschnitt, der nie vorkommt, hat den Wert 0.

Einschränkungen

0 ≤ Länge von sequence ≤ 5000

1 ≤ Anzahl der Abschnitte ≤ 10

Jeder Abschnitt hat 1 bis 8 Buchstaben

Beispiele

Beispiel 1
Eingabe:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

Erwartete Ausgabe:
expected = [3, 1]
Eingabe:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

Erwartete Ausgabe:
std::vector<long long> expected = {3, 1};
Eingabe:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};

Erwartete Ausgabe:
long[] expected = new long[] {3, 1};

Erläuterung

AGAT steht am Anfang dreimal und am Ende nur zweimal hintereinander, also bekommt es 3; CA kommt einmal vor und bekommt 1.

Beispiel 2
Eingabe:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

Erwartete Ausgabe:
expected = [3, 1, 0]
Eingabe:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};

Erwartete Ausgabe:
std::vector<long long> expected = {3, 1, 0};
Eingabe:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};

Erwartete Ausgabe:
long[] expected = new long[] {3, 1, 0};

Erläuterung

AATG wiederholt sich dreimal, TATC einmal und GATA nie: [3, 1, 0].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Spring von einer Startposition aus immer um die Länge des Abschnitts weiter, solange das nächste Stück dem Abschnitt entspricht.

Hinweis 2

Probiere jede Startposition aus und merk dir die längste Folge.

Hinweis 3

Passt ein Abschnitt nie, bleibt der beste Wert bei 0.

Erwartete Komplexität

Zeit O(n × m × k), zusätzlicher Speicher O(m)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.