Tìm chuỗi nhỏ nhất về mặt từ vựng thỏa mãn điều kiện đã cho trong Python

Giả sử chúng ta có một mảng A gồm n số, trong đó A [i] cho biết số ký tự phân biệt trong tiền tố độ dài (i + 1) của một chuỗi s, chúng ta phải tìm chuỗi nhỏ nhất về mặt từ vựng thỏa mãn mảng tiền tố đã cho. Tất cả các ký tự sẽ là bảng chữ cái tiếng Anh viết thường [a-z]. Nếu không có chuỗi như vậy thì trả về -1.

Vì vậy, nếu đầu vào là A =[1,1,2,3,4], thì đầu ra sẽ là aabcd vì tiền tố [0] có 1 ký tự riêng biệt, tiền tố [1] có 1 ký tự khác biệt, tiền tố [2] có 2 ký tự phân biệt, tiền tố [3] có 3 ký tự phân biệt, tiền tố [4] có 4 ký tự phân biệt và chuỗi là nhỏ nhất.

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

• n:=kích thước của A

• character:='a'

• string:=chuỗi trống

• nếu n <1 hoặc A [0] không phải là 1 thì

  • trả về -1

• string:=ký tự nối chuỗi

• character:=ký tự tiếp theo của ký tự hiện tại này

• đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện

  • sự khác biệt:=A [i] - A [i - 1]

  • nếu chênh lệch> 1 hoặc khác biệt <0 hoặc A [i]> 26, thì

    • trả về -1

  • ngược lại khi chênh lệch bằng 0 thì

    • string:=string concatenate 'a'

  • nếu không,

    • string:=ký tự nối chuỗi

    • character:=ký tự tiếp theo của ký tự hiện tại này

• chuỗi trả về

Ví dụ

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

def get_smallest_string(A):
   n = len(A)
   character = 'a'
   string = ""
   if (n < 1 or A[0] != 1):
      return -1
   string += str(character)
   character = chr(ord(character) + 1)
   for i in range(1, n):
      difference = A[i] - A[i - 1]
      if (difference > 1 or difference < 0 or A[i] > 26):
         return -1
      elif (difference == 0):
         string += 'a'
      else:
         string += character
         character = chr(ord(character) + 1)
return string

A = [1, 1, 2, 3, 4]
print(get_smallest_string(A))

Đầu vào

[1, 1, 2, 3, 4]

Đầu ra

aabcd