Chương trình tạo một chuỗi tối thiểu từ vựng từ hai chuỗi trong python

Giả sử, chúng ta có hai chuỗi. Chúng tôi muốn tạo một chuỗi tối thiểu về mặt từ vựng từ những chuỗi đó. Để tạo chuỗi, chúng tôi so sánh chữ cái đầu tiên của hai chuỗi và trích xuất chữ cái nhỏ hơn về mặt từ vựng từ một trong các chuỗi. Trong trường hợp hòa, tức là các chữ cái giống nhau; chúng tôi trích xuất ký tự từ chuỗi đầu tiên. Chúng tôi lặp lại quá trình này cho đến khi cả hai chuỗi đều trống. Chuỗi tối thiểu được tạo phải được trả về.

Vì vậy, nếu đầu vào giống như input_1 ='TUTORIALS', input_2 ='POINT', thì đầu ra sẽ làPOINTTUTORIALS

Nếu chúng tôi so sánh hai chuỗi, chúng tôi nhận được từng bước này -

TUTORIALS POINT
TUTORIALS OINT = P
TUTORIALS INT = PO
TUTORIALS NT = POI
TUTORIALS T = POIN
TUTORIALS = POINT

Vì một trong các chuỗi trống, toàn bộ chuỗi đầu tiên bây giờ được đặt trong chuỗi tối thiểu kết quả. Vì vậy, chuỗi cuối cùng là POINTTUTORIALS.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• input_1:=input_1 + "z"
• input_2:=input_2 + "z"
• temp_1:=0
• temp_2:=0
• res_str:=chuỗi trống
• while temp_1
• nếu input_1 [từ chỉ mục temp_1 đến cuối chuỗi]
• res_str:=res_str + input_1 [temp_1]
• temp_1:=temp_1 + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(input_1, input_2):
   input_1 += "z"
   input_2 += "z"
   temp_1 = 0
   temp_2 = 0
   res_str = ""
   while temp_1 < len(input_1) and temp_2 < len(input_2):
      if input_1[temp_1:] < input_2[temp_2:]:
         res_str += input_1[temp_1]
         temp_1 += 1
      else:
         res_str += input_2[temp_2]
         temp_2 += 1
   res_str = res_str[:-1]
   if temp_1 < len(input_1):
      res_str += input_1[temp_1:-1]
   if temp_2 < len(input_2):
      res_str += input_2[temp_2:-1]
   return res_str

print(solve('TUTORIALS', 'POINT'))

Đầu vào

'TUTORIALS', 'POINT'

Đầu ra

POINTTUTORIALS