Given a string s and a string t, check if s is subsequence of t.
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:
Input: s = "abc", t = "ahbgdc" Output: true
Example 2:
Input: s = "axc", t = "ahbgdc" Output: false
Constraints:
0 <= s.length <= 100
0 <= t.length <= 10^4
Source
def is_subsequence(s, t):
"""Using Two Pointers / Greedy
Time complexity: O(n + m)
Space complexity: O(1)
"""
if not s:
return True
if not t:
return False
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i >= len(s)
def is_subsequence(s, t):
"""Using iter()
Time complexity: O(n + m)
Space complexity: O(1)
"""
# convert t into an iterator (will return one element at a time)
# This prevents returning True in case all characters of s are in t but permuted
remainder_of_t = iter(t)
for char in s:
if char not in remainder_of_t:
return False
return True
def is_subsequence(s, t):
"""one line variation of above"""
remainder_of_t = iter(t)
return all(c in remainder_of_t for c in s) # loops through to find the 1st False. Else returns True
s = "abc"
t = "ahbgdc"
is_subsequence(s, t)
True
s = "axc"
t = "ahbgdc"
is_subsequence(s, t)
False
s = "acb"
t = "abc"
is_subsequence(s, t)
False
Solve it both iteratively and recursively
def is_subsequence(s, t):
"""Using recursion
Time Complexity: O(m+n)
Space Complexity: O(1)
"""
def helper(a, b):
# base case
if not a:
return True
if not b:
return False
# Recursion
if a[-1] == b[-1]:
return helper(a[:-1], b[:-1])
return helper(a, b[:-1])
return helper(s,t)
# Although the statement can remind us of longest subsequence problems (see leetcode #1143)
# Dynamic Programming is too slow and not relevant here since there is no need to calculate anything
def is_subsequence(s, t):
"""Using Dynamic Programming (slow, not relevant here see leetcode #1143 instead)
Time Complexity: O(mn)
Space Complexity: O(mn)
"""
if not s:
return True
if not t:
return False
n = len(s)+1
m = len(t)+1
dp = [[0]*(m) for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
if s[i-1] == t[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = dp[i][j-1]
return dp[-1][-1] == len(s)
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?
# If we check each Sk using above solution, then it would be k*O(m+n) time --> INEFICIENT
# The solution is to preprocess t and then do a binary search
# Option 1: iterative BS
def search_insert(arr, x):
"""Binary search to find the insert position of x in arr (iterative approach - See leetcode #35)"""
# base cases
if not arr or x <= arr[0]:
return 0
if arr[-1] < x:
return len(arr)
left = 0
right = len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
if arr[mid] < x:
left = mid+1
else:
right = mid-1
return left
# Option 2: recursive BS
def search_insert_recur(self, arr, x):
"""Binary search to find the insert position of x in arr (recursive approach - See leetcode #35)"""
def bs(left, right, x):
nonlocal arr
# base cases
if left > right:
return left
mid = (left + right) // 2
if x == arr[mid]:
return mid
# recursive relation
if x < arr[mid]:
return bs(left, mid - 1, x)
return bs(mid + 1, right, x)
return bs(0, len(arr)-1, x)
from collections import defaultdict
def is_subsequence(s, t):
"""Using binary search on ordered indexes (values) of Hashtable (where keys = char of s).
Time Complexity: O(n) + k* O(mlogn) with m = len(s) and n = len(t)
Space Complexity: O(m)
"""
indexes = defaultdict(list) # values of dict[keys] will be lists AND default = []
for i, char in enumerate(t):
indexes[char].append(i) # list all the indexes at which we find "element"
start = 0
for char in s:
p = search_insert(indexes[char], start) # char is present at [i1, i2, i3, ... , in]
# but we only consider t[start:] --> i.e. could we insert 'start' inside [i1, ... , in]?
if p == len(indexes[char]): # if we could not (i.e. only at the end of t)
return False
start = indexes[char][p] + 1 # if we could, we now only consider t[p+1:]
return True
from collections import defaultdict
from bisect import bisect_left
def is_subsequence(s, t):
"""Same as above but using method bisect_left (requires sorted argument)"""
indexes = defaultdict(list)
for i, char in enumerate(t):
indexes[char].append(i)
start = 0
for char in s:
p = bisect_left(indexes[char], start)
if p == len(indexes[char]):
return False
start = indexes[char][p] + 1
return True
s = "acb"
t = "ahbgdc"
is_subsequence(s, t)
False
s = "abc"
t = "ahbgdc"
is_subsequence(s, t)
True
s = "abc"
t = "ahbgdcsetezilaqzecauhpaeizokrntbziruaijzencazrkzuhtizuerbczailarbamogv"
is_subsequence(s, t)
True