Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 문자열 s의 부분 수열에 해당하는 단어 개수 찾기

단어 목록(words)과 하나의 문자열 s가 주어졌을 때, 목록에 포함된 문자열 중에서 s의 부분 수열(subsequence)에 해당하는 것의 개수를 구하는 문제입니다.

예를 들어 words = ["xz", "xw", "y"], s = "xyz"가 입력으로 주어지면 결과는 2가 됩니다. "xz"와 "y"는 "xyz"의 부분 수열이지만, "xw"는 그렇지 않기 때문입니다.

문제 해결 접근 방법

이 문제는 각 단어를 '다음에 매칭해야 할 글자'를 기준으로 버킷(bucket)에 분류한 뒤, 문자열 s를 한 글자씩 순회하며 진행 상황을 갱신하는 방식으로 효율적으로 풀 수 있습니다. 단계별 과정은 다음과 같습니다.

  • 정답 변수 ans를 0으로 초기화합니다.
  • 빈 맵(딕셔너리) d를 생성합니다.
  • words의 각 단어에 대해, 첫 글자를 키로 사용하여 d[word[0]] 리스트의 끝에 해당 단어를 추가합니다.
  • s의 각 문자 c에 대해 다음을 반복합니다.
    • l := d[c]로 현재 대기 중인 단어 목록을 가져온 뒤, d[c]는 새 리스트로 초기화합니다.
    • l의 각 단어에 대해, 단어의 길이가 1이면 모든 글자가 매칭된 것이므로 ans를 1 증가시킵니다.
    • 그렇지 않으면 첫 글자를 제거한 나머지 부분(word[1:])을 잘라내어 d[word[1]]에 추가합니다. 즉, 다음에 매칭할 글자를 키로 하여 단어를 재분류합니다.
  • 모든 순회가 끝나면 ans를 반환합니다.

이 방식은 각 단어가 s를 따라 한 번씩만 이동하므로, 전체 시간 복잡도는 단어들의 총 길이를 n, s의 길이를 m이라 할 때 O(n + m)으로 매우 효율적입니다.

구현 예제

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"

출력

2