Vergleicht man zwei Arraylisten effizient

Question

Ich bin gebeten worden, dies zu tun:

Write-Funktion Scramble (STR1, STR2), die true zurück, wenn ein Teil der str1 Zeichen neu angeordnet werden können str2 übereinstimmen, kehrt andernfalls false.

Zum Beispiel: str1 ist 'rkqodlw' und str2 ist 'world' der Ausgang sollte True zurückgeben. str1 ist 'cedewaraaossoqqyt' und str2 ist 'codewars' sollte True zurückgeben. str1 ist 'katas' und str2 ist 'steak' sollte false zurückgeben.

Es werden nur Kleinbuchstaben verwendet (a-z). Keine Interpunktion oder Ziffern sind enthalten. Leistung muss

Mein Code in Betracht gezogen werden, ist dies:

Import java.util.ArrayList;

public class Scramblies {

static ArrayList<String> strTwo = new ArrayList<String>(); 
static ArrayList<String> strOne = new ArrayList<String>(); 
static String sub1; 
static String sub2; 

public static void main (String[] args){ 

} 

public static boolean scramble(String str1, String str2) { 
boolean can = false; 
int str1length = str1.length(); 
int looping = 0; 
int counter = 0; 

    //put str1 into arraylist strOne 
    for (int i = 0; i < str1.length(); i++){ 
     sub1 = str1.substring(i); 
     for (int k = 0; k<str1.length(); k++){ 
      strOne.add(k, sub1); 
     } 
    } 

    //Put str2 into arraylist strTwo 
    for (int i = 0; i< str2.length(); i++){ 
     sub2 = str2.substring(i); 
     for (int k = 0; k < str2.length(); k++){ 
     strTwo.add(k,sub2); 
     } 

    } 

    //now search for str1 in the array strTwo. While loop so that it keeps looping the first for statement 
    while (looping != str1.length()){ 

     for (int x = 0; x < strOne.size(); x++) { 
      looping++; 
      if(strTwo.contains(strOne.get(x))) { 
        counter++; 
      } 
     }   
    } 





    if (counter == str2.length()){ //check the counter against the length of str1 (int str1length) and if they are the same then can = true 
     can = true; 
    } else { 
     can = false; 
    } 



    return can; 
} 

}

Meine Frage ist: ist dieser Code und - wenn ja - wie kann es effizienter gemacht werden. Ich denke, dass dieses Konzept funktioniert, aber es ist der Mangel an Eleganz, der mich dazu bringt, die Zeitlimits bei der Kompilierung und Ausführung des Codes in Code Wars zu versäumen.

UPDATE:

auf einige der Kommentare Basierend ich den Code aktualisiert haben und das funktioniert perfekt. Die Frage der Effizienz bleibt jedoch bestehen. Hier ist der Code:

public class Scramblies {

public static boolean scramble(String str1, String str2) { 
    String temp = str1; 
    int count = 0; 
    boolean result = true; 
    for(int i=0 ; i<str2.length() ; i++){ 
     char c = str2.charAt(i); 
     if(temp.contains(String.valueOf(c))){ 
      temp = temp.replaceFirst(String.valueOf(c), ""); 
      count++; 
     } 
    } 
    if (count == str2.length()){ 
     result = true; 
    } else { 
     result = false; 
    } 
    return result; 
} 
} 

Wenn jemand kann mir helfen bei der Herstellung dieses Code effizienten, so dass es nicht aus, Zeit, wenn gegen den Wirkungsgrad Teil des Tests laufen, das wäre sei großartig. Ich bin es auch hier gepostet: https://codereview.stackexchange.com/questions/124172/comparing-two-strings-to-see-if-string-2-is-inside-string-1

Answer 1

Sie eine Methode schreiben können, die iteriert durch jedes Zeichen von String s2 und prüft, ob es in s1 vorhanden ist, gleichzeitig die Streichhölzer Auftreten Form s1 zu entfernen, z.B .:

private static boolean canScramble(String s1, String s2){ 
    String temp = s1; 
    boolean result = true; 
    for(int i=0 ; i<s2.length() ; i++){ 
     char c = s2.charAt(i); 
     if(temp.contains(String.valueOf(c))){ 
      temp = temp.replaceFirst(String.valueOf(c), ""); 
     }else{ 
      result = false; 
      break; 
     } 
    } 
    return result; 
} 

Answer 2

Erstellen Sie ein Array von ganzen Zahlen, groß genug, um alle möglichen Zeichen (26 für Englisch) zu halten, und initialisieren auf 0

Für jedes Zeichen in der großen Zeichenfolge, erhalten die aktuelle Ganzzahl und Inkrementierung um 1. Dies stellt alle möglichen Zeichen dar, die neu angeordnet werden könnten.

Erhalten Sie für jedes Zeichen in der kleinen Zeichenfolge den aktuellen Ganzzahlwert und Dekrement um 1. Wenn der aktualisierte Wert an einem beliebigen Punkt -1 ist, kann die größere Zeichenfolge nicht neu angeordnet werden.

Nebenbei bemerkt, aus Leistungsgründen könnten Sie in Erwägung ziehen, einen rohen Zeichenpuffer anstelle einer Teilzeichenfolge zu verwenden oder einzelne Zeichen herauszuziehen.