หาสตริงที่เล็กที่สุดตามลำดับเล็กซิโคกราฟิกที่เงื่อนไขอาร์เรย์คำนำหน้าใน Python

สมมติว่าเรามีอาร์เรย์ A ขนาด n โดย A[i] บอกจำนวนตัวอักษรที่แตกต่างกันในคำนำหน้ายาว度 i+1 ของสตริง s ต้องการหาสตริงที่เล็กที่สุดตามลำดับเล็กซิโคกราฟิกที่สอดคล้องกับอาร์เรย์นี้ ตัวอักษรเป็น a-z หากไม่มี คืนค่า -1

เช่น A = [1, 1, 2, 3, 4] ผลลัพธ์คือ aabcd

ขั้นตอนการแก้ปัญหา

1. ถ้า n < 1 หรือ A[0] != 1 คืนค่า -1
2. เริ่มต้นสตริงด้วย 'a' ตัวอักษรถัดไปคือ 'b'
3. วนลูป i = 1 ถึง n-1:
   • คำนวณ difference = A[i] - A[i-1]
   • ถ้า difference > 1 หรือ < 0 หรือ A[i] > 26 คืนค่า -1
   • ถ้า difference == 0 เพิ่ม 'a' เข้าไปในสตริง
   • มิฉะนั้น เพิ่มตัวอักษรปัจจุบัน แล้วเพิ่มตัวอักษรเป็นตัวถัดไป

ตัวอย่างโค้ด Python

def get_smallest_string(A):
    n = len(A)
    character = 'a'
    string = ""
    if n < 1 or A[0] != 1:
        return -1
    string += 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))

อินพุต

[1, 1, 2, 3, 4]

เอาต์พุต

aabcd