Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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!

like image 741
snow Avatar asked Jun 11 '15 04:06

snow


People also ask

How do you check if a string contains a substring in any order?

You can use contains(), indexOf() and lastIndexOf() method to check if one String contains another String in Java or not. If a String contains another String then it's known as a substring. The indexOf() method accepts a String and returns the starting position of the string if it exists, otherwise, it will return -1.

How do you check if a string contains a sequence of characters?

lang. String. contains() method searches the sequence of characters in the given string. It returns true if sequence of char values are found in this string otherwise returns false.

How do you check if a string contains a sequence of characters Java?

Use String contains() Method to Check if a String Contains Character. Java String's contains() method checks for a particular sequence of characters present within a string. This method returns true if the specified character sequence is present within the string, otherwise, it returns false .

How do you check if a string contains a set of characters in Python?

Using Python's "in" operator The simplest and fastest way to check whether a string contains a substring or not in Python is the "in" operator . This operator returns true if the string contains the characters, otherwise, it returns false .


2 Answers

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;
}
like image 129
Caleb Rush Avatar answered Oct 06 '22 06:10

Caleb Rush


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();
}
like image 32
Shreevardhan Avatar answered Oct 06 '22 07:10

Shreevardhan