파이썬에서 단어 목록 내부에 존재하는 부분 시퀀스의 수를 찾는 프로그램

<시간/>

단어 목록과 문자열 s가 있다고 가정하고 단어 목록에서 s의 하위 시퀀스인 문자열 수를 찾아야 합니다.

따라서 입력이 단어 =["xz", "xw", "y"] s ="xyz"와 같으면 "xz"와 "y"가 "xyz"의 하위 시퀀스이므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ans :=0
d :=빈 지도
단어의 각 단어에 대해 수행
- d[word[0]] 끝에 단어 삽입
s의 각 c에 대해
- l :=d[c]
- d[c] :=새 목록
- l의 각 단어에 대해 do
  - 단어의 크기가 1이면
    - ans :=ans + 1
  - 그렇지 않으면
    - d[단어[1]] 끝에 단어[인덱스 1부터 끝까지]의 부분 문자열 삽입
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

from collections import defaultdict
class Solution:
   def solve(self, words, s):
      ans = 0

      d = defaultdict(list)
      for word in words:
         d[word[0]].append(word)

      for c in s:
         l = d[c]
         d[c] = []

         for word in l:
            if len(word) == 1:
               ans += 1
            else:
               d[word[1]].append(word[1:])
      return ans
ob = Solution()
words = ["xz", "xw", "y"]
s = "xyz"
print(ob.solve(words, s))

입력

["xz", "xw", "y"], "xyz"