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

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

ดังนั้น หากอินพุตเป็น A =[1,1,2,3,4] เอาต์พุตจะเป็น aabcd เนื่องจากคำนำหน้า[0] มีอักขระต่างกัน 1 ตัว คำนำหน้า[1] มีอักขระต่างกัน 1 ตัว คำนำหน้า[2] มีอักขระต่างกัน 2 ตัว คำนำหน้า[3] มีอักขระต่างกัน 3 ตัว คำนำหน้า[4] มีอักขระต่างกัน 4 ตัวและสตริงมีขนาดเล็กที่สุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• ตัวอักษร :='a'

• string :=สตริงว่าง

• ถ้า n <1 หรือ A[0] ไม่ใช่ 1 แล้ว

  • กลับ -1

• string :=string เชื่อมอักขระ

• อักขระ :=อักขระตัวถัดไปของอักขระปัจจุบันนี้

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • ความแตกต่าง :=A[i] - A[i - 1]

  • ถ้าความแตกต่าง> 1 หรือความแตกต่าง <0 หรือ A[i]> 26 แล้ว

    • กลับ -1

  • มิฉะนั้นเมื่อผลต่างเท่ากับ 0 แล้ว

    • string :=string เชื่อม 'a'

  • มิฉะนั้น

    • string :=string เชื่อมอักขระ

    • อักขระ :=อักขระตัวถัดไปของอักขระปัจจุบันนี้

• สตริงส่งคืน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

[1, 1, 2, 3, 4]

ผลลัพธ์

aabcd