392.Is Subsequence

Tags: [two_pointers], [map]

Link: https://leetcode.com/problems/is-subsequence/?tab=Description

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 bothsandt.tis potentially a very long (length ~= 500,000) string, andsis 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"

Returntrue.

Example 2:
s="axc",t="ahbgdc"

Returnfalse.

Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to@pbrotherfor adding this problem and creating all test cases.

Solution: two pointers

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if not s:
            return True
        if not t:
            return not s

        s_index = 0
        t_index = 0
        s_len = len(s)
        t_len = len(t)

        while s_index < s_len and t_index < t_len:
            s_c = s[s_index]
            t_c = t[t_index]

            if s_c == t_c:
                s_index += 1
            t_index += 1

        return s_index == s_len

Note:

• Time complexity = O(max(s_len, t_len)), s_len is the length of the s string, and t_len is the length of the t string.

Follow up solution: map

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if not s:
            return True
        if not t:
            return not s

        t_c_map = {}
        for i in xrange(len(t)):
            c = t[i]
            if c in t_c_map:
                t_c_map[c].append(i)
            else:
                t_c_map[c] = [i]

        curr_t_index = -1
        for c in s:
            if c not in t_c_map or not t_c_map[c] or t_c_map[c][-1] <= curr_t_index:
                return False

            t_indexes = t_c_map[c]
            t_tmp_index = 0
            while t_tmp_index < len(t_indexes):
                if t_indexes[t_tmp_index] > curr_t_index:
                    break

            # we must can find one t index is greater than curr_t_index
            curr_t_index = t_indexes[t_tmp_index]
            t_c_map[c] = t_indexes[t_tmp_index + 1:]

        return True

Revelation:

• When we build the t_c_map, for each char, we append the t index of the char into an array. Because we iterate the t's chars one by one from left to right, so the t indexes have already been sorted in each array.

Note:

• Time complexity = O(t + s * t) = O(s * t), s is the length of string s, and t is the length of string t. But think about if s is far more less t, and there are a lot of s need to be checked, we only need counting t's char and indexes once. So this solution maybe faster than under this scenario.