Lösen Sie komplexe Probleme mit Rekursion

Optimierte Codierung

Rekursion: Wenn sich eine Funktion direkt oder indirekt selbst aufruft, indem sie das Problem in kleinere Teilmengen aufteilt.

Im Grunde genommen ist Rekursion ein einfacher Stack, bei dem Sie Ihre Methode wiederholt pushen und poppen , um das Endergebnis zu erzielen.

Wie unten gezeigt, werden die Methoden auf einen Stapel verschoben, bis die Grundbedingung erreicht ist. Sobald die Basisbedingung erfüllt ist, wird die Methode zurückverfolgt oder aus dem Stapel entfernt.

Dieser Artikel wird unter der Annahme erklärt, dass Sie über grundlegende Programmierkenntnisse verfügen.

Nehmen wir ein Beispiel für das folgende Leetcode-Problem.

Unterteile eine gegebene Zeichenfolge sso, dass jede Teilzeichenfolge der Partition ein Palindrom ist. Gibt alle möglichen Palindrom-Partitionierungen vons zurück .

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Beim Codieren geht es darum, Probleme in Stücke zu zerlegen und sie zu lösen. Bevor wir die Technik zum Knacken des Problems analysieren, werden wir die notwendigen Variablen analysieren und deklarieren. Vor dem Deklarieren sollten Sie daran denken, nur erforderliche Variablen mit weniger Platzkomplexität zu deklarieren.

1. Suchen Sie den Datentyp der erforderlichen Variablen

List<List<String>> result = new ArrayList<List<String>>();
List<String> strArray = new ArrayList<String>();

Das Motiv des Problems besteht darin, herauszufinden, ob die Teilketten Palindrome sind. Wenn ein Wort auch umgekehrt dieselbe Bedeutung hat, spricht man von einem Palindrom. Hier müssen wir alle möglichen Teilstrings finden, um herauszufinden, ob Palindrom oder nicht. Wenn der Teilstring ein Palindrom ist, fügen wir ihn dem Array hinzu, andernfalls wird er übersprungen.

3. Finden Sie die Grundbedingungen

Für alle Probleme müssen Grundbedingungen vorhanden sein, um die Rekursion zu stoppen. In unserem Fall können wir die Schleife unterbrechen, wenn der Iterator der Zeichenfolge die Länge der Zeichenfolge überschreitet.

if(start>=s.length()){
    result.add(new ArrayList<String>(strArray));
}

Die nächste Aufgabe besteht darin, herauszufinden, wann die Bedingungen zu durchlaufen sind. Wenn festgestellt wird, dass eine Teilzeichenfolge ein Palindrom ist, müssen wir die Rekursion starten, um zu überprüfen, ob auch die nächsten Zeichen der Zeichenfolgen ein Palindrom bilden. Wenn es kein Palindrom ist, können wir die nächste Zeichenfolge iterieren.

Um den Teilstring zu finden, wird der gegebene String zerlegt und iteriert, um das Array zu bilden.

Es ist klar, dass wir die gegebene Zeichenfolge einzeln durchlaufen und auch Rekursion verwenden müssen, um alle Teilzeichenfolgen zu finden.

Während der ersten Iteration der gegebenen Eingabe wird die Zeichenfolge a genommen. Prüfen Sie, ob es sich um ein Palindrom handelt oder nicht. Wenn Palindrom der Liste hinzugefügt wird und die Rekursion entlang der Zeichenfolge beginnt, bis die Grundbedingung erfüllt ist. Wenn die Basisbedingung erfüllt ist, fügen Sie dem Ergebnis eine Liste hinzu und verfolgen Sie die Zeile zurück, um nach anderen möglichen Teilzeichenfolgen zu suchen.

Ebenso für die zweite und dritte Iteration . Iterieren Sie bis zur Basisbedingung, um die möglichen Teilzeichenfolgen zu finden.

Mit derselben Logik und durch Ändern von Code können Sie die meisten Rekursionsprobleme lösen.

import java.util.*;
class Solution {

  public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<List<String>>();
    List<String> strArray = new ArrayList<String>();
    backTrack(0, s, result, strArray);
    return result;
  }

  public void backTrack(int start, String s, List<List<String>> result,  List<String> strArray) {
    if (start >= s.length()) {
      result.add(new ArrayList<String>(strArray));
    }

    for (int itr = start; itr < s.length(); itr++) {
      if (isPalindrome(s, start, itr)) {
        strArray.add(s.substring(start, itr + 1));
        backTrack(itr + 1, s, result, strArray);
        strArray.remove(strArray.size() - 1);
        
      }
    }
  }

  public boolean isPalindrome(String str, int start, int end) {
    while (start < end) {
      if (str.charAt(start++) != str.charAt(end--)) return false;
    }
    return true;
  }
}

Kommentieren Sie Ihre nützlichen Codierungstechniken.

Finde mich hier:

www.linkedin.com/in/p-divya