Ungültige Klammern Zeitkomplexität entfernen

Question

Versuchen Sie, Laufzeit von unten Algorithmus für Problem zu verstehen; Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results

Dies ist eine einfache BFS-Lösung, die alle möglichen Zeichenfolgen durch Entfernen von "(" oder ")" generiert.

public List<String> removeInvalidParentheses(String s) { 
    List<String> ret = new LinkedList<>(); 
    Set<String> visited = new HashSet<>(); 
    Queue<String> queue = new LinkedList<>(); 
    queue.add(s); 
    while (!queue.isEmpty()) { 
     String current = queue.poll(); 
     if (isValidParentheses(current)) { 
      ret.add(current); 
     } 
     if (ret.size() > 0) continue; 
     for (int i = 0; i < current.length(); i++) { 
      if (current.charAt(i) == '(' || current.charAt(i) == ')') { 
       String next = current.substring(0, i) + current.substring(i + 1); 
       if (!visited.contains(next)) { 
        visited.add(next); 
        queue.offer(next); 
       } 
      } 
     } 
    } 
    return ret; 
} 

public boolean isValidParentheses(String current) { 
    int open = 0; 
    int close = 0; 
    for (char c : current.toCharArray()) { 
     if (c == '(') open++; 
     else if (c == ')') close++; 
     if (close > open) return false; 
    } 
    return open == close; 
} 

Es beginnt mit erzeugen n möglich Strings und nächste Stufe es alle Strings mit einer Größe von n-1 Länge erzeugen, und n-2 Länge, etc .. für )()( Beispiel

   )()(    len n 
    ()( ))( ()( )()  n-1 
    () ((()       n-2 

jede Ebene es prüft alle möglichen Strings mit n-Level Länge. angesichts dieser - Ich hatte schwer zu Zeit herauszufinden, wie die Laufzeit dieses Algorithmus finalisieren. Wie generalisiere ich diesen Algorithmus und analysiere die Komplexität?

Answer 1

Für den schlimmsten Fall, versuchen Sie es mit Eingabe als ((((. Gemäß der obigen Logik wird (((( in die Warteschlange geschoben und überprüft, ob dies ungültig ist. Es würde also 4 weitere mögliche Teilstrings der Länge 3 erzeugen, die sie in die Warteschlange schieben würden. Bei der Verarbeitung dieser Warteschlangenelemente würde es wieder mehr Strings der Länge 2 für jede Teilkette der Länge 3, dann für zwei und dann für das Ende erzeugen. Wir gehen davon aus, dass T (1) = 1.

Wenn Sie versuchen, eine Rekursion für die obige Logik zu machen, wäre es

T(n) = nT(n-1) + 1 sein, die als

geschrieben werden können

 = `n((n-1)T(n-2) + 1) + 1` and so on. 

On Wenn wir es komplett lösen würden, würden wir T(n) = n! + n(n-1)/2 + 1 bekommen, was O(n!) wäre.

Daher denke ich, dass die Zeitkomplexität der Ordnung O(n!) Weitere Informationen darüber, wie wäre zu lösen verweisen die Rekursion T(n) = nT(n-1) + 1, bitte: this post on its solution