Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution(object):
- def numMatchingSubseq(self, s, words):
- """
- :type s: str
- :type words: List[str]
- :rtype: int
- """
- n = len(s)
- alphabets = {chr(97+i): [] for i in range(26)}
- for i, e in enumerate(s):
- alphabets[e].append(i)
- ans = 0
- for word in words:
- flag = True
- start = 0
- m = len(word)
- for indx, letter in enumerate(word):
- end = n-m+indx
- indexes = alphabets[letter]
- if len(indexes) == 0 or indexes[-1] < start or end < indexes[0]:
- flag = False
- break
- if start <= indexes[0]:
- start = indexes[0] + 1
- continue
- l = 1
- r = len(indexes) - 1
- mid = (l+r)//2
- while(True):
- if l > r:
- start = indexes[l]+ 1
- break
- if indexes[mid] == start:
- start = indexes[mid]+ 1
- break
- if start <indexes[mid]:
- r = mid- 1
- else:
- l= mid+ 1
- mid = (l+r)//2
- if flag == True:
- ans+= 1
- return ans
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement