Cách kiểm tra xem chuỗi có chứa chuỗi thứ hai có các ký tự trong thứ tự không?

Question

Tôi mới bắt đầu và tôi hoàn toàn bị mất về cách thực hiện việc này.

Tôi muốn có thể kiểm tra chuỗi cho chuỗi nhỏ hơn và trả về true nếu chuỗi chứa các chữ cái của chuỗi theo thứ tự.

Tôi không chắc chắn làm thế nào để đi về việc đảm bảo các chữ cái của chuỗi thứ hai là theo thứ tự, ngay cả khi có các chữ cái khác giữa chúng.

Ví dụ sẽ là "hóa học" sẽ trả về true cho chuỗi "lần truy cập".

Nó sẽ trả về false cho chuỗi "anh ấy".

Mọi trợ giúp sẽ được đánh giá cao.

EDIT: Cảm ơn bạn, tôi đã thay đổi từ "chuỗi con" thành chuỗi. Như tôi đã nói, tôi chỉ mới bắt đầu và không nhận thức được điều đó có nghĩa là cái gì khác. Tôi thực sự đánh giá cao tất cả sự giúp đỡ. Nó sẽ giúp tôi đi đúng hướng.

Answer 1

SInce bạn chưa đăng bất kỳ mã nào, tôi sẽ chỉ giải thích tôi sẽ làm gì.

• lặp qua tất cả các thư chuỗi con bằng thư, trên ví dụ của bạn "nhấn"
• Kiểm tra xem lá thư hiện tại (lặp 0 là h) là trên chuỗi, nếu/khi nó tìm thấy bạn loại bỏ các ocurrences trước và để chuỗi đó từ đó (emistry)
• Thực hiện quy trình này cho tất cả các đế trái
• sử dụng biến boolean điều khiển để xem liệu biến đó có tìm thấy hay không.
• nếu trong bất kỳ lần chuyển nào của lần lặp lại bạn không thấy bạn trả về false.

Answer 2

Vâng, bạn có thể đi qua cả hai dây cùng một lúc, tiến chỉ số của mình vào "chuỗi" (cụm từ đúng là dãy - "sương mù" là một chuỗi con của "hóa học", nhưng "nhấn" duy nhất là một chuỗi) chỉ khi ký tự hiện tại của nó khớp với ký tự hiện tại trong chuỗi bên ngoài. Tức là, đối với "hóa học" và "nhấn", bạn bắt đầu với chỉ số i = 0, j = 0. Bạn tăng chỉ số i vào chuỗi đầu tiên cho đến khi bạn gặp phải s1.charAt(i) == s2.charAt(j), đó là trường hợp của i = 1 (ký tự thứ hai trong hóa học là h). Sau đó, bạn tăng j và hiện đang tăng i một lần nữa cho đến khi bạn nhấn "i" (i = 4). Chuỗi thứ hai được chứa như là một chuỗi trong lần đầu tiên nếu ở cuối, j == s2.length() giữ. Lưu ý rằng ở đây - không giống như các vấn đề phức tạp hơn, chẳng hạn như kiểm tra xem chuỗi thứ hai có thực sự là một chuỗi phụ hay không. so với hiện tại trong một trong chuỗi thứ hai; bạn luôn có thể "tham lam" chọn cái đầu tiên bạn nhìn thấy.

Hoặc, bạn có thể sử dụng regexes: chuyển chuỗi thứ hai (tìm kiếm) thành mẫu regex String pat = ".*h.*i.*t.*" và kiểm tra s1.matches(pat).

Answer 3

Cách tiếp cận chung là lặp qua các ký tự của chuỗi dài hơn ("hóa học"), luôn theo dõi chỉ số của ký tự được yêu cầu tiếp theo từ chuỗi ngắn hơn ("hit" — đầu tiên 0, sau đó 1 một lần bạn tìm h, sau đó 2 khi bạn tìm thấy i, và sau đó khi bạn tìm thấy t bạn đã hoàn tất). Ví dụ:

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

Bạn có thể làm như sau (không chắc chắn hiệu quả như thế nào là):

1. Hãy xem xét tìm kiếm của bạn chuỗi "hit" như một mảng của char: [ "h", "i "," t "]
2. Sử dụng chỉ mụcOf (c) để xác định xem ký tự đầu tiên trong mảng có thể được tìm thấy hay không.
3. Lặp lại tìm kiếm trên chuỗi con còn lại.

Dưới đây là các mã:

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

Một câu trả lời chút thay đổi dựa trên @ ruakh của giải pháp:

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() là từ Java 7, nhớ để thay thế cho một cái gì đó tương tự (từ Apache Commons's StringUtils?) nếu bạn không sử dụng Java 7. Xác nhận giả định trả về false phù hợp cho một chuỗi hoặc chuỗi trống hoặc bạn có thể muốn xem xét việc ném một thứ gì đó như IllegalArgumentException.

Hai câu lệnh if đã được kết hợp thành một mệnh đề duy nhất cho độ chặt.

chỉnh sửa: Nếu một trong số đó là nghiêng về mặt toán học hoặc sau giải pháp gốc của ruakh, bất kỳ trình tự nào cũng sẽ chứa một chuỗi trống. Lý do duy nhất tại sao mã của tôi ở trên là làm điều đó một cách khác nhau là vì tôi thích tưởng tượng một đối số trống dưới dạng một đối số không hợp lệ, do đó trả về false. Nó thực sự phụ thuộc vào phương pháp này được sử dụng như thế nào, và làm thế nào 'nghiêm trọng' một đối số rỗng là.

Answer 6

Tôi biết điều này đã được hỏi là câu hỏi Java. Nhưng chỉ để tham khảo, đây là một phiên bản của nó trong 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; 
} 

để biên dịch: gcc -Wall -Wextra main.c -o main

main self elf

main chemistry try

main chemistry hit

main chemistry tim