The followup solution should not use binary search


  • 0
    A

    Suppose the t's length is n, there K smaller strings and the smaller string is of length m.
    The binary search solution would be of time complexity O(n + KMlogn).

    But if we use a brute force method to build the dictionary for each char with the indices of the all the next chars, the time complexity is O(n^2). But we only need O(m) to decide if a string is a subsequence. The overall time complexity is O(n^2 + KM).

    It is easy to test that the second is more efficient when K is really large.

    But the code would not pass the test cases here. Down vote this question.


Log in to reply
 

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