โปรแกรมหาจำนวนคู่ของสตริงย่อยที่เท่ากันใน Python

สมมติว่าเราได้รับสองสตริง ทั้งสองทำจากอักษรตัวพิมพ์เล็ก เราต้องหาจำนวนสี่เท่า (p, q, r, s) ที่ตรงตามเงื่อนไขที่กำหนด -

• 0 <=p <=q <=ความยาวของสตริงแรก

• 0 <=r <=s <=ความยาวของสตริงที่สอง

• สตริงย่อยเริ่มต้นที่ดัชนี p ของสตริงแรกและสิ้นสุดที่ดัชนี q ของสตริงแรก ต้องเท่ากับสตริงย่อยที่เริ่มต้นที่ดัชนี q ของสตริงที่สองและสิ้นสุดที่ดัชนี r ของสตริงที่สอง

• q - r ต้องเป็นค่าต่ำสุดที่เป็นไปได้ภายในสี่เท่าทั้งหมดที่เป็นไปตามข้างต้น

เราต้องหาจำนวนสี่เท่านั้นให้ได้

ดังนั้น หากอินพุตเป็นเหมือน firstString ='hgfn', secondString ='gfrt' ผลลัพธ์จะเป็น 2

มีสองสี่ (1, 1, 0, 0) และ (2, 2, 1, 1) ที่ตรงตามเงื่อนไขและมีค่าต่ำสุดสำหรับ q - r.

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

• กำหนดฟังก์ชัน ord() นี่จะใช้เวลา ch
  • คืนค่ายูนิโค้ดของ ch
• จากวิธีหลัก ให้ทำดังนี้ -
• ซ้าย :=รายการใหม่ของขนาด 26 ที่มีค่าอินฟินิตี้
• right :=รายการใหม่ของขนาด 26 ที่มีค่า -1
• res :=0
• mi :=อินฟินิตี้
• สำหรับแต่ละดัชนี i และอักขระ ch ใน firstString ให้ทำ
  • left[ord(ch) - ord('a') ] :=ขั้นต่ำของ (left[ord(ch) - ord('a') ], i)
• สำหรับแต่ละดัชนี i และอักขระ ch ใน secondString ให้ทำ
  • right[ord(ch) - ord('a') ] :=สูงสุดของ right[ord(ch) - ord('a') ], i
• สำหรับฉันในช่วง 0 ถึง 25 ทำ
  • ถ้า left[i] ไม่เหมือนกับ -1 แล้ว
    • mi :=ขั้นต่ำของ (mi, left[i] - right[i])
• สำหรับฉันในช่วง 0 ถึง 25 ทำ
  • ถ้า left[i] ไม่เหมือนกับอินฟินิตี้ และ right[i] ไม่เหมือนกับ -1 แล้ว
    • ถ้า left[i] - right[i] เหมือนกับ mi แล้ว
      • res :=res + 1
• ผลตอบแทน

ตัวอย่าง

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

def solve(firstString, secondString):
   left = [float('inf')] * 26
   right = [-1] * 26
   res = 0
   mi = float('inf')
   for i, ch in enumerate(firstString):
      left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
   for i, ch in enumerate(secondString):
      right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
   for i in range(26):
      if left[i] != -1:
         mi = min(mi, left[i] - right[i])
   for i in range(26):
      if left[i] != float('inf') and right[i] != -1:
         if left[i] - right[i] == mi:
            res += 1
   return res

print(solve('hgfn', 'gfrt'))

อินพุต

'hgfn', 'gfrt'

ผลลัพธ์

2