Wie kann man wissen, ob eine Zeichenfolge in zwei Strings segmentiert werden kann

Question

Ich wurde im Interview folgenden Frage gestellt. Ich konnte nicht herausfinden, wie ich diese Frage angehen sollte. Bitte führen Sie mich.

Frage: Wie man erkennt, ob eine Schnur in zwei Stränge segmentiert werden kann - wie Brotbanana ist segmentierbar in Brot und Banane, während Brotbanan nicht ist. Sie erhalten ein Wörterbuch, das alle gültigen Wörter enthält.

Answer 1

Erstellen Sie eine trie der Wörter, die Sie im Wörterbuch haben, die Suche schneller machen wird. Durchsuchen Sie den Baum anhand der folgenden Buchstaben Ihrer Eingabezeichenfolge. Wenn Sie ein Wort gefunden haben, das sich in der Baumstruktur befindet, beginnen Sie rekursiv mit der Position nach dem Wort in der Eingabezeichenfolge. Wenn Sie das Ende der Eingabezeichenfolge erreichen, haben Sie eine mögliche Fragmentierung gefunden. Wenn Sie stecken geblieben sind, kommen Sie zurück und versuchen Sie rekursiv ein anderes Wort.

EDIT: Entschuldigung, verpasste die Tatsache, dass es nur zwei Worte sein muss. In diesem Fall begrenzen die Rekursionstiefe 2.

Der Pseudo-Code für 2 Worte sei:

T = trie of words in the dictionary 
for every word in T, which can be found going down the tree by choosing the next letter of the input string each time we move to the child: 
    p <- length(word) 
    if T contains input_string[p:length(intput_string)]: 
     return true 
return false 

Unter der Annahme, können Sie zu einem untergeordneten Knoten in der Trie in O(1) (ascii-Indizes von Kindern nach unten gehen), können Sie alle Präfixe der Eingabezeichenfolge in O(n+p) finden, wobei die Anzahl der Präfixe und n die Länge des Eingangs ist. Obere Grenze ist O(n+m), wobei m die Anzahl der Wörter im Wörterbuch ist. Die Prüfung auf containing dauert O(w) wobei w die Länge des Wortes ist, für das die obere Grenze m wäre, so dass die Zeitkomplexität des Algorithmus O(nm) ist, da O(n) in der ersten Phase zwischen allen gefundenen Wörtern verteilt wird.

Aber weil wir in der ersten Phase nicht mehr als n Wörter finden können, ist die Komplexität auch auf O(n^2) beschränkt. So würde die Suchkomplexität sein O(n*min(n, m)) Vor diesem müssen Sie den Trie bauen, der O(s) nehmen wird, wobei s die Summe der Längen der Wörter im Wörterbuch ist. Die obere Schranke ist O(n*m), da die maximale Länge jedes Wortes n ist.

Answer 2

Die einfachste Lösung:

Split die Zeichenfolge zwischen jedem Paar von aufeinanderfolgenden Zeichen und sehen, ob sie beiden Teile (links vom Split-Punkt und rechts davon) ist im Wörterbuch.

Answer 3

Ein Ansatz könnte sein:

Put all elements of dictionary in some set or list jetzt können Sie contains & substring Funktion verwenden Wörter zu entfernen, das Wörterbuch übereinstimmt. wenn am Ende der String null ist -> String kann segmentiert werden sonst nicht. Sie können auch auf zählen achten.

Answer 4

public boolean canBeSegmented(String s) { 
    for (String word : dictionary.getWords()) { 
     if (s.contains(word) { 
      String sub = s.subString(0, s.indexOf(word)); 
      s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1); 
     } 

     return s.equals(""); 
    } 
} 

Dieser Code überprüft, ob der angegebene String vollständig segmentiert werden kann. Es prüft, ob ein Wort aus dem Wörterbuch innerhalb Ihrer Zeichenfolge ist und subtrahiert es. Wenn Sie es in den Prozess segmentieren möchten, müssen Sie die subtrahierten Semente in der Reihenfolge bestellen, in der sie sich innerhalb des Wortes befinden.

Nur zwei Worte macht es einfacher:

public boolean canBeSegmented(String s) { 
    boolean wordDetected = false; 

    for (String word : dictionary.getWords()) { 
     if (s.contains(word) { 
      String sub = s.subString(0, s.indexOf(word)); 
      s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1); 

      if(!wordDetected) 
       wordDetected = true; 
      else 
       return s.equals(""); 
     } 

     return false; 
    } 
} 

Dieser Code prüft, ob ein Wort, und wenn es ein anderes Wort im String ist und nur diese beiden Worte es gibt true zurück, andernfalls false.

Answer 5

Sie gehen durch Ihr Wörterbuch und vergleichen jeden Begriff als Teilzeichenfolge mit dem ursprünglichen Begriff z. "Brotbanane". Wenn der erste Ausdruck mit dem ersten Teilstring übereinstimmt, schneide den ersten Ausdruck aus dem ursprünglichen Suchbegriff heraus und vergleiche die nächsten Wörterbucheinträge mit dem Rest des ursprünglichen Begriffs ...

Lassen Sie mich versuchen, das in Java zu erklären: z.B

String dictTerm = "bread"; 
    String original = "breadbanana"; 

    // first part matches 
    if (dictTerm.equals(original.substring(0, dictTerm.length()))) { 
     // first part matches, get the rest 
     String lastPart = original.substring(dictTerm.length()); 

     String nextDictTerm = "banana"; 

     if (nextDictTerm.equals(lastPart)) { 
      System.out.println("String " + original + 
       " contains the dictionary terms " + 
       dictTerm + " and " + lastPart); 
     } 
    } 

Answer 6

dies eine bloße Idee ist, können Sie es besser implementieren, wenn Sie

package farzi; 

import java.util.ArrayList; 

public class StringPossibility { 
    public static void main(String[] args) { 
     String str = "breadbanana"; 
     ArrayList<String> dict = new ArrayList<String>(); 
     dict.add("bread"); 
     dict.add("banana"); 
     for(int i=0;i<str.length();i++) 
     { 
      String word1 = str.substring(0,i); 
      String word2 = str.substring(i,str.length()); 
      System.out.println(word1+"===>>>"+word2); 
      if(dict.contains(word1)) 
      { 
       System.out.println("word 1 found : "+word1+" at index "+i); 
      } 
      if(dict.contains(word2)) 
      { 
       System.out.println("word 2 found : "+ word2+" at index "+i); 
      } 
     } 

    } 

}