โปรแกรมหาสตริงเล็กสุดตามลำดับเล็กซิโครกราฟิกด้วยการสลับครั้งเดียวใน Python

สมมติว่ามีสตริง s เราต้องหาสตริงที่เล็กที่สุดตามลำดับเล็กซิโครกราฟิกที่สามารถสร้างได้หากเราสลับตัวอักษรสองตัวใน s ได้สูงสุดหนึ่งครั้ง

เช่น ถ้าอินพุตคือ "zyzx" ผลลัพธ์จะเป็น "xyzz"

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

• temp := อาร์เรย์ขนาด s เติม 0
• m := len(s) - 1
• for i จาก len(s)-1 ถึง 0
  • ถ้า s[i] < s[m] m := i
  • temp[i] := m
• for i ในช่วง 0 ถึง len(s)
  • a := temp[i]
  • ถ้า s[a] != s[i] คืนค่า s[:i] + s[a] + s[i+1:a] + s[i] + s[a+1:]
• คืนค่า s

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

class Solution:
    def solve(self, s):
        temp = [0] * len(s)
        m = len(s) - 1
        for i in range(len(s)-1, -1, -1):
            if s[i] < s[m]:
                m = i
            temp[i] = m
        for i in range(len(s)):
            a = temp[i]
            if s[a] != s[i]:
                return s[:i] + s[a] + s[i+1:a] + s[i] + s[a+1:]
        return s

ob = Solution()
print(ob.solve("zyzx"))

อินพุต

zyzx

เอาต์พุต

xyzz