-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path392.py
More file actions
80 lines (57 loc) · 1.66 KB
/
392.py
File metadata and controls
80 lines (57 loc) · 1.66 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
'''
392. Is Subsequence
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
both s and t. t is potentially a very long (length ~= 500,000)
string, and s is 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"
Return true.
Example 2:
s = "axc", t = "ahbgdc"
Return false.
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?
'''
class Solution(object):
def isSubSequence_2(self, s, t):
if len(t) < len(s):
return False
for l in s:
temp = t.find(l)
if temp == -1:
return False
t = t[temp + 1:]
return True
# runtime 392 ms
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
jt = 0
js = 0
while jt < len(t) and js < len(s):
while t[jt] != s[js] and jt < len(t) - 1:
print(t[jt])
jt += 1
jt += 1
js += 1
if js < len(s):
return False
else:
return True
def test():
s = "abc"
t = "ahgbdc"
sol = Solution()
print(sol.isSubSequence_2(s, t))
if __name__ == "__main__":
test()