Quiz 1
Can you optimize the following code?
# This problem is "392. Is Subsequence" in LeetCode. Here is the description.
# Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
# A subsequence of a string is a new string that is formed from the original string by deleting
# some (can be none) of the characters without disturbing the relative positions of the remaining
# characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
for c in t:
if len(s) == 0:
return True
if s[0] == c:
s = s[1:]
return len(s) == 0
Answer
Let S = len(s) and T = len(t). The time complexity is O(T + S^2) in the worst case.
We still scan all of t, and every time we do s = s[1:] we create a new string,
which costs O(S) each. That slicing happens at most S times, so the total slicing
cost is O(S^2). The extra space complexity is O(1), but each slice allocates a new string of size up to O(S).
We can remove the unnecessary copying by using one pointer and a single pass.
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
for c in t:
if i == len(s):
break
if c == s[i]:
i += 1 # increment so i reaches len(s) when fully matched
return i == len(s)
This improved logic has O(T) time complexity and O(1) extra space.