Python에서 두 문자열의 가장 큰 병합을 찾는 프로그램

두 개의 문자열 s와 t가 있다고 가정합니다. 우리는 다음과 같은 방식으로 merge라는 문자열을 형성하기를 원합니다. s 또는 t가 비어 있지 않은 동안 다음 옵션 중 하나를 선택하십시오 -

• s가 비어 있지 않은 경우 s의 첫 번째 문자를 추가하여 s에서 병합 및 삭제합니다.

• t가 비어 있지 않은 경우 t의 첫 번째 문자를 추가하여 t에서 병합하고 삭제합니다.

마지막으로 우리가 형성할 수 있는 사전순으로 가장 큰 병합을 찾아야 합니다.

따라서 입력이 s ="zxyxx" t ="yzxxx"와 같으면 출력은 "zyzxyxxxxx"가 됩니다.

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

• a :=0, b :=0

• 병합 :=빈 문자열

• W1 :=s의 크기

• W2 :=t의 크기

• 동안

  • 인덱스 a에서 끝까지 s의 부분 문자열> 인덱스 b에서 끝까지 t의 부분 문자열인 경우

    • 병합 :=병합 병합 s[a]

    • a :=a + 1

  • 그렇지 않으면

    • 병합 :=병합 병합 t[b]

    • b :=b + 1

• 반환 병합 연결(인덱스 a에서 끝까지 s의 부분 문자열) 연결(인덱스 b에서 끝까지 t의 부분 문자열)

예

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

def solve(s, t):
   a = b = 0
   merge = ""

   W1 = len(s)
   W2 = len(t)
   while a < W1 and b < W2:
      if s[a:] > t[b:]:
         merge += s[a]
         a += 1
      else:
         merge += t[b]
         b += 1

   return merge + s[a:] + t[b:]

s = "zxyxx"
t = "yzxxx"
print(solve(s, t))

입력

"zxyxx", "yzxxx"

출력

zyzxyxxxxx