Abrufen eines Teilstrings aus einem exponentiell wachsenden String

Question

Für die Ganzzahl A ist die Basisstufe 1 "XYZ". Für nachfolgende Stufen werden die Stufen zu "X" + Stufe (A - 1) + "Y" + Stufe (A - 1) + "Z". Für Level 2 wäre die Zeichenfolge also "XXYZYXYZZ".

Ziel ist es, die Teilzeichenfolge mithilfe des Start- und Endindex aus der Level-Zeichenfolge zurückzugeben.

Beispiel: Wenn Sie 2 3 7 eingeben, wird Level 2, 3. bis 7. Zeichen angezeigt, und das Ergebnis ist "YZYXY" von "XXYZYXYZZ".

Die folgenden Einschränkungen sind angegeben:

• 1 ≦ Stufe K ≦ 50,
• 1 ≦ Start ≦ Ende ≦ Länge des Level K Strings,
• 1 ≦ Ende - Start + 1 ≦ 100.

Ich habe einen Brute-Force-Ansatz für dieses Problem in Python wie folgt geschrieben

def my_substring():
    level = int(input())
    start_index = int(input()) - 1
    end_index = int(input())
    strings_list = [None] * level
    strings_list[0] = "XYZ"

    for i in range(1, level):
        strings_list[i] = "X" + strings_list[i - 1] + "Y" + strings_list[i - 1] + "Z"

    return "".join(strings_list[-1])[start_index:end_index]


if __name__ == '__main__':
    print(my_substring())

Wie gezeigt, erhöht sich die Länge der Zeichenfolge für jede Iteration um (Basiszeichenfolge * 2) + 3. Nach der 20. Iteration stößt mein Programm auf Probleme, weil ich mich mit der enormen endgültigen Zeichenfolge befassen muss. Ich möchte lernen, wie ich meine Komplexität von dem, was ich für O (N ^ 2) halte, reduzieren kann.

Welche alternativen Ansätze gibt es für mich, um sehr lange Zeichenfolgen in Python zu verarbeiten / zu verketten? Gibt es eine Möglichkeit für mich, die Ladezeit / Ressourcen für das Verdoppeln meiner Zeichenfolgen zu reduzieren?

Oder ist mein aktueller Ansatz fehlerhaft und sollte ich dieses Problem aus einem anderen Blickwinkel angehen (für den ich bisher keine Alternative finden kann).

Bearbeiten: Mir wurde gesagt, dass dieses Problem in O (1) - O (logn) Zeit gelöst werden kann.

Answer 1

Die Länge der Zeichenfolge auf Ebene \$ K \$ist \$ 3 (2^K -1) \$, was bedeutet, dass für \$ K = 50 \$eine Zeichenfolge mit \$ 3377699720527869 \$Zeichen wird (rekursiv) erstellt. Das sind ungefähr 3 Petabyte (wenn Sie ein Byte pro Zeichen zählen) und passen nicht in den Speicher Ihres Computers.

Andererseits wird aufgrund der Einschränkung \ nur ein kleiner Teil dieser vollständigen Zeichenfolge tatsächlich benötigt$ 1 \le end - start + 1 \le 100 \$. In vielen Fällen ist diese Teilzeichenfolge bereits in der Zeichenfolge enthalten, die von einer vorherigen, kleineren Ebene angegeben wurde.

Daher würde ich einen rekursiven Algorithmus bevorzugen: Überprüfen Sie die angegebenen Start- und Endindizes für die Positionen "X", "Y" und "Z" von der aktuellen Ebene und kehren Sie für die Teile zwischen diesen Positionen zur vorhergehenden Ebene zurück.

Hier ist eine mögliche Implementierung:

def substring(level, start_index, end_index):
    # Indices of "X", "Z", "Y" at the current level:
    low = 1
    high = 3 * (2 ** level - 1)
    mid = (low + high) // 2

    result = ""
    while start_index <= end_index:
        if start_index == low:
            result += "X"
            start_index += 1
        elif start_index < mid:
            e = min(end_index, mid - 1)
            result += substring(level - 1, start_index - low, e - low)
            start_index += e - start_index + 1
        elif start_index == mid:
            result += "Y"
            start_index += 1
        elif start_index < high:
            e = min(end_index, high - 1)
            result += substring(level - 1, start_index - mid, e - mid)
            start_index += e - start_index + 1
        else:
            result += "Z"
            start_index += 1

    return result

Es berechnet

substring(50, 3377699720527869-200, 3377699720527869-100)

innerhalb von Sekundenbruchteilen.

Weitere Verbesserungen sind möglich, z. B. indem festgestellt wird, dass die Zeichenfolge auf Ebene K mit K "X" -Zeichen beginnt und mit K "Z" -Zeichen endet, oder indem die erste Ebene separat behandelt wird.

Answer 2

Benutzereingabe

Zunächst ist es wichtig, jedes Mal eine Eingabeaufforderungszeichenfolge anzugeben input. Derzeit wird dem Benutzer eine leere Konsole angezeigt. Er hat nicht einmal einen Hinweis darauf, dass Sie darauf warten, dass er etwas eingibt. Nach allem, was sie wissen, ist das Programm nur aufgehängt. Mach stattdessen so etwas wie

level = int(input('Please enter the level.'))

Diese inputAufrufe sollten sich auf derselben (äußeren) Ebene wie Ihre befinden printund nicht in der my_substringRoutine enthalten sein. my_substringsollte ganzzahlige Parameter akzeptieren.

String-Interpolation

Verwenden Sie einen F-String. etwas wie

strings[i] = f'X{strings[i - 1]}Y{strings[i - 1]Z'

Benennung

Im Allgemeinen können Sie es stattdessen strings_listeinfach aufrufen strings- der Plural ist ein Hinweis des Programmierers, dass dies iterierbar ist, und Sie können einen tatsächlichen : List[str]Typhinweis hinzufügen, um anzuzeigen, dass es sich um eine Zeichenfolgenliste handelt.

Algorithmus

Anstatt eine Zeichenfolgenverkettung innerhalb der Schleife (und anstelle einer F-Zeichenfolge) durchzuführen, prüfen Sie, ob sich Ihre Laufzeit durch Einfügen von Listen verbessert. Sie werden immer noch einen joinetwas erweiterten Index erstellen.