Advertisement
DeepRest

Number of Matching Subsequences

Jun 22nd, 2021
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. class Solution(object):
  2. def numMatchingSubseq(self, s, words):
  3. """
  4. :type s: str
  5. :type words: List[str]
  6. :rtype: int
  7. """
  8.  
  9. n = len(s)
  10.  
  11. alphabets = {chr(97+i): [] for i in range(26)}
  12. for i, e in enumerate(s):
  13. alphabets[e].append(i)
  14.  
  15. ans = 0
  16. for word in words:
  17. flag = True
  18. start = 0
  19. m = len(word)
  20.  
  21. for indx, letter in enumerate(word):
  22. end = n-m+indx
  23. indexes = alphabets[letter]
  24.  
  25. if len(indexes) == 0 or indexes[-1] < start or end < indexes[0]:
  26. flag = False
  27. break
  28. if start <= indexes[0]:
  29. start = indexes[0] + 1
  30. continue
  31.  
  32. l = 1
  33. r = len(indexes) - 1
  34. mid = (l+r)//2
  35. while(True):
  36. if l > r:
  37. start = indexes[l]+ 1
  38. break
  39. if indexes[mid] == start:
  40. start = indexes[mid]+ 1
  41. break
  42. if start <indexes[mid]:
  43. r = mid- 1
  44. else:
  45. l= mid+ 1
  46. mid = (l+r)//2
  47.  
  48. if flag == True:
  49. ans+= 1
  50.  
  51. return ans
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement