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!

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

Answer 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();
}