Python에서 가장 긴 anagram 부분 시퀀스의 길이를 찾는 프로그램

<시간/>

두 개의 소문자 문자열 S와 T가 있다고 가정하고 가장 긴 아나그램 하위 시퀀스의 길이를 찾아야 합니다.

따라서 입력이 S ="helloworld", T ="hellold"와 같으면 출력은 8

이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −
c :=새 지도, d :=새 지도
범위 0에서 크기까지의 i에 대해
- c에서 a[i]이면
  - c[a[i]] :=c[a[i]] + 1
- 그렇지 않으면
  - c[a[i]] :=1
범위 0에서 b 크기까지의 i에 대해
- b[i]가 d이면
  - d[b[i]] :=d[b[i]] + 1
- 그렇지 않으면
  - d[b[i]] :=1
해상도 :=0
c의 각 ch에 대해 수행
- d[ch]> 0이면
  - res :=res + c[ch] 및 d[ch]의 최소값
반환 해상도

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

예시

class Solution:
   def solve(self, a, b):
      c, d = {}, {}
      for i in range(len(a)):
         if a[i] in c:
            c[a[i]] += 1
         else:
            c[a[i]] = 1
      for i in range(len(b)):
         if b[i] in d:
            d[b[i]] += 1
         else:
            d[b[i]] = 1
      res = 0
      for ch in c:
         if d.get(ch, 0) > 0:
            res += min(c[ch], d[ch])
         return res
ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))

입력

S = "helloworld", T = "hellorld"