Efficient solution for the follow-up question.

  • 0

    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?

    My solution is to pre-compute an index. The index is built as a linked list. Each node is as follows (in Python style):

    class ListNode(object):
        def __init__(self, letter):
            self.val = letter # a letter
            self.next_a = None # link to the ListNode of next 'a'
            self.next_b = None # link to the ListNode of next 'b'
            self.next_z = None # link to the ListNode of next 'z'

    Process all the letters in T to build this index. This can be done in O(len(T)) time and O(len(T)) space (using DP). Then, for each Si, the execution time is O(len(Si)).

    The following is an illustration, where we suppose 'a', 'b', 'c' are all possible letters.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.