Wie erhält man alle möglichen Zeichenpaare einer gegebenen Zeichenkette?

Question

Ich habe eine Zeichenfolge "Orakel". Ich möchte mögliche Zeichenpaare erhalten. Ich habe es versucht und konnte es in o(n*n) tun. Ich suche nach einer optimierten Lösung. Können wir es in weniger als o(n*n) lösen?

Input : oracle 
Output : "or" "oa", "oc", "ol", "oe" , "ra", "rc", "rl", "re" , "ac", "al", "ae", "cl", "ce", "le" 

Answer 1

Nein, es ist nicht möglich, weil die Ausgabegröße auf O(n*n) basiert. Abhängig von den genauen Anforderungen ist es entweder bis n*(n-1) oder n*(n-1)/2 (wenn wir die Reihenfolge von dem ursprünglichen Wort beibehalten müssen).

Answer 2

String string = "oracle"; 
    HashMap occurs = new HashMap(); 

    for(int i=0; i<string.length(); i++) 
     occurs.put(""+string.charAt(i), new Boolean(true)); 

    for(char a='a'; a < 'z'; a++) 
     if(occurs.get(""+a)!=null) 
      for(char b=(char) (a+1); b<'z'; b++) 
       if(occurs.get(""+b)!=null) 
        System.out.print(a+""+b+" "); 

Es ist in linearer Zeit möglich.
Zuerst benötigen Sie ein boolesches Array (! Für konstante Nachschlagezeiten) aller Zeichen im Alphabet und durchlaufen über die zu überprüfende Zeichenfolge, welche Zeichen enthalten sind. (linear)
Zweitens müssen Sie über alle möglichen Zeichenpaare iterieren und nach beiden Zeichen suchen, wenn sie enthalten waren. Wenn also die entsprechenden booleschen Werte sind, true. (konstant)

ich einige Code zur Verfügung stellen kann, wenn erforderlich

Greets!