Как проверить, содержит ли строка String вторую строчку с ее символами в порядке?

Question

Я только начинаю, и я полностью потерял, как это сделать.

Я хочу, чтобы проверить строку для меньшей строки и вернуть значение true, если строка содержит буквы строки в порядке.

Я не уверен, как сделать так, чтобы буквы второй строки были в порядке, даже если между ними есть другие буквы.

Примером может служить то, что «химия» вернет true для строки «hit».

Это вернет false для строки «он».

Любая помощь была бы принята с благодарностью.

EDIT: Спасибо, я изменил слово «подстрока» на строку. Как я уже сказал, я только начинаю и не знал, что это значит что-то другое. Я очень ценю всю помощь. Это должно заставить меня двигаться в правильном направлении.

Answer 1

SInce Вы не разместили ни одного кода, я просто объясню, что бы я сделал.

• перебрать все буквы подстроки в письме, на вашем примере «хит»
• Проверьте, если текущая буква (итерация 0 ч) на строке, если/когда это найти вы удалите вхождения перед тем это и пусть строка из этого (emistry)
• Сделайте этот процесс для всех левых подстрок
• используйте контрольную логическую переменную, чтобы узнать, найден ли она или нет.
• Если в любом проходе итерации вы не нашли, что возвращаете false.

Answer 2

Ну, вы могли бы пройти через обе строки одновременно, продвигая свой индекс к «подстроки» (правильный термин подпоследовательности - «туман» подстрока «химии», но «удар» только подпоследовательность), только если ее текущий символ совпадает с текущим символом во внешней строке. I.e., для «химии» и «хита» вы начинаете с индексов i = 0, j = 0. Вы увеличиваете индекс i в первую строку до тех пор, пока не найдете s1.charAt(i) == s2.charAt(j), что соответствует i = 1 (второй символ в химии - h). Затем вы увеличиваете j и теперь увеличиваете i, пока не нажмете «i» (i = 4). Вторая строка содержится в качестве подпоследовательности в первом, если в конце выполняется j == s2.length(). Обратите внимание, что здесь - в отличие от более сложных проблем, таких как тестирование, если вторая строка действительно является подстрокой . - жадная стратегия работает, то есть вам не нужно беспокоиться о , который из нескольких вхождений того же символа, который вы соответствуете против тока в одном во второй строке; вы всегда можете «жадно» выбрать первый, который видите.

В качестве альтернативы вы можете использовать регулярные выражения: преобразовать вторую строку поиска в шаблон регулярного выражения String pat = ".*h.*i.*t.*" и тест s1.matches(pat).

Answer 3

Общий подход состоит в том, чтобы перебирать символы более длинной строки («химия»), всегда отслеживая индекс следующего обязательного символа из более короткой строки («hit» — first 0, затем 1 раз, когда вы найдите h, затем 2, как только вы найдете i, а затем, когда вы найдете t, все готово). Например:

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

Вы можете сделать следующее (не уверен, насколько эффективно это):

1. Рассмотрим поиска строку «хит» как массив полукокса: [ «ч», "Я "," t "]
2. Используйте indexOf (c), чтобы определить, можно ли найти первый символ в массиве.
3. Повторите поиск на оставшейся подстроке.

Вот код:

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

Немного измененная ответ, основанный на @ ruakh решение которого:

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() от Java 7, не забудьте заменить что-то подобное (с Apache Commons's StringUtils?), если вы не на Java 7. Предполагается, что возврат false подходит для пустой последовательности или подпоследовательности, или вы можете захотеть бросить что-то вроде IllegalArgumentException.

Два заявления if были объединены в единое положение для компактности.

Редактировать: Если какой-либо математически наклонный или исходное решение @ ruakh, любая последовательность должна содержать пустую подпоследовательность. Единственная причина, почему мой код выше делает это по-другому, заключается в том, что я предпочитаю представлять пустой аргумент как форму недопустимого аргумента, возвращая false. Это действительно зависит от того, как этот метод используется, и как «серьезный» пустой аргумент.

Answer 6

Я знаю, что это задавали как вопрос Java. Но только для справки, вот версия этого в С \

#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; 
} 

компиляции: gcc -Wall -Wextra main.c -o main

main self elf

main chemistry try

main chemistry hit

main chemistry tim