How to check if a String contains a second string with its characters in order?

Question

I am just starting, and I completely lost how to do it.

I want to be able to check a string for a smaller string and return true if the string contains the letters of the string in order.

I'm not sure how to make the letters of the second line be in order, even if there are other letters between them.

An example is the fact that "chemistry" will return true for the string "hit".

It will return false for the string "he", though.

Any help would be greatly appreciated.

EDIT: Thanks, I changed the word "substring" to a string. As I said, I'm just starting out and did not know that it means something else. I really appreciate all the help. That should make me move in the right direction.

Answer 1

A general approach is to iterate over characters of a longer string ("chemistry"), always tracking the index of the next required character from a shorter string ("hit" - first 0, then 1 as soon as you find h , then 2 as soon as you will find i , and then when you find t , you are done). For instance:

 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 2

If you didn’t post any code, I’ll just explain what I would do.

• Iterate over the entire letter of a substring letter, for your example "hit"
• Make sure the current letter (iteration 0 is equal to h) is in the line if / when it detects that you delete it before that, and let the line from this (emistry)
• Make this process for all left substrings
• use a control boolean variable to find out if it is found or not.
• If in any iteration pass you did not find that you are returning false.

Answer 3

Well, you could go through both lines at the same time, moving your index to the "substring" (the correct term is subsequence - "fog" is the substring "chemistry", but only "hit" is only a subsequence) if its current character matches the current character in the outer line. Ie, for “chemistry” and “hit” you start with indices i = 0, j = 0 . You increase the index i to the first line until you meet s1.charAt(i) == s2.charAt(j) , which is the case for i = 1 (the second character in chemistry is h). Then you increase j and now increase i until you press "i" ( i = 4 ). The second line is contained in the subsequence in the first, if at the end, j == s2.length() is executed. Please note that here - unlike more complex problems such as testing, if the second line is really a substring - the greedy strategy works, that is, you do not need to worry about which of several occurrences of the same character matches the current one in one in the second line; you can always “greedily” choose the first one you see.

Alternatively, you can use regular expressions: convert the second string (search) into a regular expression pattern String pat = ".*h.*i.*t.*" s1.matches(pat) String pat = ".*h.*i.*t.*" s1.matches(pat) String pat = ".*h.*i.*t.*" And check s1.matches(pat) .

Answer 4

You can do the following (not sure how effective it is):

• Consider your search string "hit" as an array of char: ["h", "i", "t"]
• Use indexOf (c) to determine if the first character can be found in the array.
• Repeat the search on the remaining substring.

Here is the 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

A slightly modified answer based on @ruakh's solution:

 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() from Java 7, do not forget to replace something like this (from Apache Commons StringUtils ?) If you are not in Java 7. Assumes that returning false is suitable for an empty sequence or subsequence, or you may want to throw something- something like IllegalArgumentException .

Two if were combined into a single sentence for compactness.

edit: If someone is mathematically inclined or after the original @ruakh solution, any sequence should contain an empty subsequence. The only reason why my code above does it differently is because I prefer to represent an empty argument as a form of an invalid argument, thereby returning false . It really depends on how this method is used, and as a “serious” empty argument.

Answer 6

I know this was asked as a Java question. But for reference only, here is its version 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; } 

to compile: gcc -Wall -Wextra main.c -o main

main self elf

main chemistry try

main chemistry hit

main chemistry tim