Wie verwende ich den Go Java-Algorithmus zur String-Dekodierung?

String-Dekodierung

Gibt bei einer gegebenen codierten Zeichenfolge die decodierte Zeichenfolge zurück.

Die Kodierungsregel lautet: k[encoded_string], was bedeutet, dass der encoded_string in den eckigen Klammern k-mal wiederholt wird. Beachten Sie, dass k garantiert eine positive ganze Zahl ist.

Sie können davon ausgehen, dass die Eingabezeichenfolge immer gültig ist; die Eingabezeichenfolge enthält keine zusätzlichen Leerzeichen und die eingegebenen eckigen Klammern erfüllen immer die Formatanforderungen.

Darüber hinaus können Sie davon ausgehen, dass die Originaldaten keine Zahlen enthalten, sondern nur die Anzahl der Wiederholungen k. Es wird beispielsweise keine Eingabe wie 3a oder 2 geben.

• Beispiel 1:

Eingabe: s = „3[a]2[bc]“

Ausgabe: „aaabcbc“

• Beispiel 2:

Eingabe: s = „3[a2[c]]“

Ausgabe: „ccaccacc“

• Beispiel 3:

Eingabe: s = „2[abc]3[cd]ef“

Ausgabe: „abcabccdcdcdef "

• Beispiel 4:

Eingabe: s = "abc3[cd]xyz"

Ausgabe: "abccdcdcdxyz"

Methode 1: Stapel (Java)

Sehen Sie sich die Zuordnung von Klammern an, Das erste, was mir in den Sinn kommen sollte, ist, den Stack zur Lösung des Problems zu verwenden.

Da die Nummer mehr als eine Ziffer haben kann, können Sie aus Gründen der Übersichtlichkeit und Bequemlichkeit zunächst zwei Stapel verwenden, einen zum Speichern von Zahlen und einen zum Speichern von Zeichen. Wenn ein anderes Zeichen als ] angetroffen wird, wird es zuerst in den Zeichenstapel eingefügt. Wenn eine Zahl angetroffen wird, wird die vollständige Zahl umgewandelt und in den Zahlenstapel eingefügt. Wenn ] angetroffen wird, werden die Zeichen bis zu [ herausgeholt Erstellen Sie aus dem Zeichenstapel eine temporäre Zeichenfolge und entfernen Sie das oberste Element des Zahlenstapels. Wiederholen Sie die temporäre Zeichenfolge so oft und legen Sie sie dann wieder in den Zeichenstapel ein.

Nachdem die ursprüngliche Zeichenfolge von links nach rechts durchlaufen wurde, ist das Element im Stapel die endgültige Antwort ) Und schieben Sie es auf den Stapel

Wenn das aktuelle Zeichen ein Buchstabe oder eine linke Klammer ist, schieben Sie es direkt auf den Stapel
Wenn das aktuelle Zeichen eine rechte Klammer ist, beginnen Sie damit, es vom Stapel zu entfernen, bis das Die Reihenfolge, in der die linke Klammer geknallt wird, wird umgekehrt. Für eine Zeichenfolge ist die zu diesem Zeitpunkt herausgenommene Zahl oben auf dem Stapel die Häufigkeit, mit der diese Zeichenfolge angezeigt werden soll Zahl und die Zeichenfolge und schiebe sie auf den Stapel. Daher können wir darüber nachdenken, die Rekursion zu verwenden, um es zu vervollständigen. Spezifische rekursive Ideen finden Sie unten.

• Das Verschachtelungsproblem zwischen mehreren Klammern muss gelöst werden. Das heißt, überlappende Teilprobleme. Sie können Stapel oder Rekursion verwenden, um Probleme zu lösen.

• 1. Identifizieren Sie zunächst die Position, an der die rechte Klammer endet.

2. Wenn Sie auf eine linke Klammer stoßen, wird i+1 an das nächste Mal übergeben.

3 Beenden Sie die Operation der linken Klammer und setzen Sie die Anzahl der Produkte auf Null, i = die Position, an der sich die letzte befindet rechte Klammer berührt. Fügen Sie weiterhin die restlichen Zeichen außerhalb der rechten Klammer hinzu.

Spezifische Idee: Analysieren Sie die Zeichenfolge von links nach rechts:

• Wenn die aktuelle Position eine Ziffer ist, muss sie eine Zeichenfolge enthalten, die durch eckige Klammern dargestellt wird. Dies ist der Fall: k[...]:

• Wir können zuerst eine Zahl analysieren, dann die linke Klammer analysieren, den folgenden Inhalt rekursiv analysieren und zurückkehren, wenn wir auf die entsprechende rechte Klammer stoßen. Zu diesem Zeitpunkt können wir die Zahl x basierend auf der analysierten Zahl analysieren Die Zeichenfolge s' in den Klammern erstellt eine neue Zeichenfolge. Die aktuelle Position ist eine Buchstabenposition, daher analysieren wir direkt den aktuellen Buchstaben und analysieren dann den Inhalt nach diesem Buchstaben rekursiv nach unten.

• class Solution {
      int ptr;
      public String decodeString(String s) {
          LinkedList<String> stk = new LinkedList<String>();
          ptr = 0;
          while (ptr < s.length()) {
              char cur = s.charAt(ptr);
              if (Character.isDigit(cur)) {
                  // 获取一个数字并进栈
                  String digits = getDigits(s);
                  stk.addLast(digits);
              } else if (Character.isLetter(cur) || cur == &#39;[&#39;) {
                  // 获取一个字母并进栈
                  stk.addLast(String.valueOf(s.charAt(ptr++))); 
              } else {
                  ++ptr;
                  LinkedList<String> sub = new LinkedList<String>();
                  while (!"[".equals(stk.peekLast())) {
                      sub.addLast(stk.removeLast());
                  }
                  Collections.reverse(sub);
                  // 左括号出栈
                  stk.removeLast();
                  // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                  int repTime = Integer.parseInt(stk.removeLast());
                  StringBuffer t = new StringBuffer();
                  String o = getString(sub);
                  // 构造字符串
                  while (repTime-- > 0) {
                      t.append(o);
                  }
                  // 将构造好的字符串入栈
                  stk.addLast(t.toString());
              }
          }
          return getString(stk);
      }
      public String getDigits(String s) {
          StringBuffer ret = new StringBuffer();
          while (Character.isDigit(s.charAt(ptr))) {
              ret.append(s.charAt(ptr++));
          }
          return ret.toString();
      }
      public String getString(LinkedList<String> v) {
          StringBuffer ret = new StringBuffer();
          for (String s : v) {
              ret.append(s);
          }
          return ret.toString();
      }
  }

  Zeitkomplexität: O(N)

Raumkomplexität: O(N)

Das obige ist der detaillierte Inhalt vonWie verwende ich den Go Java-Algorithmus zur String-Dekodierung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!