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

สมมติว่าเรามีสตริง S และ T สองสตริง เราต้องตรวจสอบว่าสตริงที่มีความยาวเท่ากันซึ่งใหญ่กว่า S และเล็กกว่า T หรือไม่ เราต้องคืนค่า -1 หากไม่มีสตริงดังกล่าว เราต้องจำไว้ว่า S =S1S2… Sn ถูกเรียกว่า lexicographically น้อยกว่า T =T1T2… Tn หากมี i ดังนั้น S1=T1, S2=T2, … Si – 1=Ti – 1, ซิ <ติ.

ดังนั้น หากอินพุตเป็น S ="bbb" และ T ="ddd" เอาต์พุตจะเป็น "bbc"

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

• n :=ขนาดของสตริง
• สำหรับฉันในช่วง n - 1 ถึง 0, ลดลง 1 ทำ
  • ถ้า string[i] ไม่เหมือนกับ 'z' ดังนั้น
    • k :=ASCII ของ (สตริง[i])
    • string[i] :=อักขระจาก ASCII (k + 1)
    • รวมอักขระสตริงและส่งคืน
  • string[i] :='a'

ตัวอย่าง

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

def find_next(string):
   n = len(string)
   for i in range(n - 1, -1, -1):
      if string[i] != 'z':
         k = ord(string[i])
         string[i] = chr(k + 1)
         return ''.join(string)
      string[i] = 'a'
S = "bbb"
T = "ddd"
S = list(S)
res = find_next(S)
if res != T:
   print(res)
else:
   print(-1)

อินพุต

"bbb", "ddd"

ผลลัพธ์

bbc