Check if string contains the substring's sequence of characters in order, but not necessarily right next to each other

Question

Given two strings, return true if the first string contains the second string's sequence of characters in order, but not necessarily right next to each other.

For example, String : "I am hungry and want food right now", Substring: "mto". The substring where o comes before t in the sentence does not count, they have to be in order but not necessarily right next to each other.

I'm not really looking for code, just in general how would you solve this problem!

Solution 1

Usually when you first encounter a problem, you should evaluate how you yourself would solve the problem before considering how you would program a computer to do so.

If you try and solve your example problem yourself, you'll most likely start with the first character in the second string, 'm', and search for the first appearance of that character in the string. Once you find the 'm' at the 3rd index position, you'll then evaluate from the 4th index on to find the next letter in the substring. You'll continue to evaluate until one of two things happen:

1. You cannot find one of the letters. This means that the result is false.
2. You run out of letters in the substring. This means that the result is true.

If you understand how to solve the problem yourself, it's just a matter of breaking the solution down into steps.

You didn't ask for it, but in the off chance it makes it more clear, here's a simple method to solve the problem:

public static boolean sub(String string, String substring) {
    // Keep track of our position in the string.
    int index = 0;

    // Iterate through all of the characters in the substring.
    for (char character : substring.toCharArray()) {
        // Find the current character starting from the last character we stopped on.
        index = string.indexOf(character, index);
        // If the method returned -1, the character was not found, so the result is false.
        if (index == -1)
            return false;
    }

    // If we reach this point, that means all characters were found, so the result is true.
    return true;
}

Solution 2

A simple implementation would be like

Traverse both strings from one side to other. If find a matching character, move ahead in both strings. Otherwise move ahead only in s2.

bool isSubSequence(std::string s1, std::string s2) {
    int j = 0;
    for (int i = 0; i < s2.length() && j < s1.length(); ++i)
        if (s1[j] == s2[i])
            ++j;
    return j == s1.length();
}

Solution 3

Just use O(N) greedy algorithm maybe?

As you say you do not need code, I describe the steps as following: Let S be the string and P be the pattern

1. Maintain a pointer PT to P, initially pointing at the front of P
2. For each character in S, check if S[i] equals to the character in P pointing by the PT
3. If yes, move PT to next character of P, if it is last character you found it

Solution 4

You will have to search the string one Substring character at a time. Since you said you didn't need code, I'll try to explain how in words (with some Java API calls for reference).

For each character in the Substring, find the first occurrence of that character in String (in this case, 'm', then 't', then 'o'). You can do this with a call to String.indexOf(String char). Keep track of the index that character is found and when you search String for the next character (in this case 't'), look in the subset of String starting at that index using String.substring(idx, -1).indexOf(String char). The -1 will search from the index of the previously found character ('m') until the end of the string.

Keep iterating though the characters of Substring, and one of two things will happen. The first is that you will not find the character in the subset of String, which means that the Substring is not in there in order. The second possibility is that you will come to the end of Substring and all the characters will have been found in order.

View more solutions