Is 'abc' subsequence of 'ahbgdc'?

Problem

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

s = "abc", t = "ahbgdc"

Return true.

Example 2:

s = "axc", t = "ahbgdc"

Return false.

This problem is taken from LeetCode, [Problem 392, Is Subsequence] (https://leetcode.com/problems/is-subsequence/)

Analysis

Example 2 shows that the sequence of the s is important. We cannot use String.contains() to get the answer directly.

Main idea:

1. Check the 1st character of t and s.
2. If the 1st character of t is same as 1st character of s, then check the 2nd character of t with 2nd character of s.
3. If the 1st character of t is not same as 1st character of s, check the 2nd character of t with 1st character of s until the whole string of t is checked.

Solution 1

public boolean isSubsequence(String s, String t) {
    boolean result = false;
    int j = 0; //index of s

    for(int i=0; i < t.length(); i++){

        //j < s.length() to avoid out of bound error
        if(j < s.length() && t.charAt(i) == s.charAt(j)){
            j++;
        }
    }

    //if j < s.length(), means not all characters of t are matched with s
    result = j == s.length();

    return result;
}

Solution 2 (Faster version)

public boolean isSubsequence(String s, String t)
{
    if(t.length() < s.length()) return false;

    int prevIndex = 0;
    for(int i = 0; i < s.length(); i++)
    {
        char tempChar = s.charAt(i);
        prevIndex = t.indexOf(tempChar, prevIndex);

        if(prevIndex == -1) return false;
        prevIndex++;
    }

    return true;
}

indexOf(int char, int fromIndex) is the magic line to make the checking process faster.