Wie überprüft man, ob ein String einen zweiten String mit seinen Zeichen in der Reihenfolge enthält?

Question

Ich fange gerade an und ich bin völlig verloren, wie man das macht.

Ich möchte eine Zeichenfolge für eine kleinere Zeichenfolge überprüfen und True zurückgeben, wenn die Zeichenfolge die Buchstaben der Zeichenfolge in der Reihenfolge enthält.

Ich bin mir nicht sicher, wie ich sicherstellen soll, dass die Buchstaben der zweiten Zeichenfolge in Ordnung sind, auch wenn andere Buchstaben dazwischen stehen.

Ein Beispiel wäre, dass "Chemie" für die Zeichenfolge "Hit" True zurückgegeben würde.

Es würde jedoch falsch für die Zeichenfolge "ihn" zurückgeben.

Jede Hilfe würde sehr geschätzt werden.

EDIT: Danke, ich habe das Wort "substring" in string geändert. Wie gesagt, ich fange gerade erst an und wusste nicht, dass das etwas anderes bedeutet. Ich schätze wirklich all die Hilfe. Es sollte mich in die richtige Richtung bewegen.

Answer 1

Wenn Sie keinen Code geschrieben haben, werde ich nur erklären, was ich tun würde.

• Iterate über alle Teilzeichen Buchstaben für Buchstaben, auf Ihrem Beispiel „Hit“
• Überprüfen Sie, ob der aktuelle Brief (Iterierte 0 h) ist auf der Saite, ob/wann es finden Sie die ocurrences entfernen, bevor es und lassen sie die Zeichenfolge aus, dass (emistry)
• sie diesen Vorgang für alle linken Teil
• eine Steuer boolean Variable verwenden, um festzustellen, ob es oder nicht gefunden hat.
• Wenn Sie in einem Durchgang der Iteration nicht gefunden haben, geben Sie false zurück.

Answer 2

Nun, man gleichzeitig durch beiden Saiten gehen könnte, Ihren Index auf die „Teilzeichen“ voran (der richtige Begriff ist Teilfolge - „Nebel“ ist ein Teilwort von „Chemie“, aber „Hit“ ist nur eine Untersequenz) nur dann, wenn das aktuelle Zeichen mit dem aktuellen Zeichen in der äußeren Zeichenfolge übereinstimmt. Das heißt, für "Chemie" und "Treffer" beginnen Sie mit den Indizes i = 0, j = 0. Sie erhöhen den Index i in die erste Zeichenfolge, bis Sie auf s1.charAt(i) == s2.charAt(j) stoßen, was für i = 1 der Fall ist (zweites Zeichen in Chemie ist h). Dann erhöhen Sie und erhöhen jetzt wieder i bis Sie ein "i" (i = 4) treffen. Die zweite Zeichenfolge ist als Untersequenz in der ersten enthalten, wenn am Ende j == s2.length() gilt. Beachten Sie, dass hier - im Gegensatz zu komplexeren Problemen wie dem Testen, ob die zweite Zeichenkette wirklich eine Teilzeichenfolge ist - eine gierige Strategie funktioniert, was bedeutet, dass Sie sich keine Gedanken über mehrerer Vorkommen desselben Zeichens machen müssen gegen den Strom in einem in der zweiten Schnur; Sie können immer "gierig" das erste auswählen, das Sie sehen.

Alternativ können Sie Regexes verwenden: Konvertieren Sie die zweite (Such-) Zeichenfolge in das Regex-Muster String pat = ".*h.*i.*t.*", und testen Sie s1.matches(pat).

Answer 3

Der allgemeine Ansatz besteht darin, über die Zeichen der längeren Zeichenfolge ("Chemie") zu iterieren, immer den Index des nächsten erforderlichen Zeichens aus der kürzeren Zeichenfolge zu verfolgen ("hit" — zuerst 0, dann 1 einmal Finden Sie h, dann 2 einmal finden Sie i, und dann, wenn Sie t finden Sie fertig sind). Zum Beispiel:

public static boolean containsSubsequence(
     final String sequence, final String subsequence) { 
    if (subsequence.isEmpty()) { 
     return true; 
    } 
    int subsequenceIndex = 0; 
    for (int i = 0; i < sequence.length(); ++i) { 
     if (sequence.charAt(i) == subsequence.charAt(subsequenceIndex)) { 
      ++subsequenceIndex; 
      if (subsequenceIndex == subsequence.length()) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

Answer 4

Sie konnten die folgende (nicht sicher, wie effizient es ist) tun:

1. Ihr Suchbegriff "Hit" als ein Array von char Bedenken Sie: [ "h", "i "," t "]
2. Verwenden Sie indexOf (c), um festzustellen, ob das erste Zeichen im Array gefunden werden kann.
3. Wiederholen Sie die Suche für die verbleibende Teilzeichenfolge.

Hier ist der Code:

public class SearchString { 
    public static void main(String[] args) { 
     String searchSpace = "this is where to search?"; 
     String needle = "tweus?"; 
     char[] chars = needle.toCharArray(); 
     int index = 0; 
     boolean found = true; 
     int startIndex = 0; 
     while (found && index < chars.length){ 
      searchSpace = searchSpace.substring(startIndex); 
      startIndex = searchSpace.indexOf(chars[index]); 
      found = (startIndex != -1); 
      index++; 
     } 
     if (index==chars.length && found){ 
      System.out.println("Found it"); 
     } else { 
      System.out.println("Nothing here"); 
     } 
    } 
} 

Answer 5

Eine leicht modifizierte Antwort basierend auf @ Lösung ruakh suchen:

public static boolean containsSubsequence(final String sequence, final String subsequence) { 
    if (Objects.requireNonNull(sequence).isEmpty() || Objects.requireNonNull(subsequence).isEmpty() || subsequence.length() > sequence.length()) { 
     return false; 
    } 
    int index = 0; 
    for (int i = 0; i < sequence.length(); i++) { 
     if (sequence.charAt(i) == subsequence.charAt(index) && ++index == subsequence.length()) { 
      return true; 
     } 
    } 
    return false; 
} 

Objects.requireNonNull() ist von Java 7, denken Sie daran für etwas ähnliches (von Apache Commons's StringUtils zu ersetzen?) Wenn Sie nicht auf Java 7 sind. Die Validierung setzt voraus, dass false für eine leere Sequenz oder Untersequenz geeignet ist, oder Sie sollten in Erwägung ziehen, etwas wiezu werfen.

Die beiden if Anweisungen wurden zu einer einzigen Klausel für die Kompaktheit zusammengefasst.

edit: Wenn man mathematisch geneigt ist oder der ursprünglichen Lösung von @ ruakh folgt, sollte jede Sequenz eine leere Subsequenz enthalten. Der einzige Grund, warum mein Code oben anders ist, ist, weil ich es vorziehe, ein leeres Argument als eine Form eines ungültigen Arguments vorzustellen und so false zurückgibt. Es hängt wirklich davon ab, wie diese Methode verwendet wird und wie "streng" ein leeres Argument ist.

Answer 6

Ich weiß, dass dies als eine Java-Frage gestellt wurde. Aber gerade als Referenz, hier ist eine Version davon in C \

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <ctype.h> 

int find_str_in_str(const char* const base, const char* const sub) 
{ 
     int base_len = strlen(base); 
     int sub_len = strlen(sub);  
     char *tmp_sub = NULL; 

     /* allocate enough mem for the max string length */ 
     if(base_len > sub_len) { 
       tmp_sub = malloc(base_len + 1); 
     } else { 
       tmp_sub = malloc(sub_len + 1); 
     } 

     if(NULL == tmp_sub) { 
       fprintf(stderr, "Runtime error (malloc)\n"); 
       exit(1); 
     } 

     int i = 0; 
     int j = 0; 

     for(; i < sub_len; i++) { 
       for(; j < base_len; j++) { 
         if(base[j] == sub[i]) { 
           tmp_sub[i] = base[j]; 
           /* the first occurance was found */ 
           break; 
         } 
       } 
     } 

     tmp_sub[i++] = '\0'; 

     if(0 == strcmp(sub, tmp_sub)) { 
       free(tmp_sub); 
       return 1; 
     } else { 
       free(tmp_sub); 
       return 0; 
     } 
} 





int main(int argc, char **argv) 
{ 
     if(argc < 3) { 
       fprintf(stderr, "Usage: %s %s %s\n", argv[0], "base", "derived"); 
       return EXIT_FAILURE; 
     } 

     if(1 == find_str_in_str(argv[1], argv[2])) { 
       printf("true\n"); 
     } else { 
       printf("false\n"); 
     } 
     return EXIT_SUCCESS; 
} 

zu kompilieren: gcc -Wall -Wextra main.c -o main

main self elf

main chemistry try

main chemistry hit

main chemistry tim