โปรแกรมตรวจสอบว่ามี permutation ที่มากกว่าหรือน้อยกว่า lexicographically ระหว่างสองสตริงใน Python

สมมติว่ามีสตริง s และ t ความยาวเท่ากัน ต้องการตรวจสอบว่ามี permutation s1 ของ s และ t1 ของ t ที่ทำให้ s1[i] <= t1[i] สำหทุก i หรือ t1[i] <= s1[i] สำหทุก i

ตัวอย่าง: s = "vyx", t = "wzx" ผลลัพธ์ True เลือก s1 = "vxy", t1 = "wxz"

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

1. ถ้า s และ t ว่าง: คืน True
2. เรียง s และ t
3. ฟังก์ชัน util(s1, t1): วน i ถ้า s1[i] > t1[i] คืน False, จบคืน True
4. ถ้า util(s, t) จริง: คืน True
5. สลับ s, t คืน util(s, t)

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

class Solution:
    def solve(self, s, t):
        if not len(s) or not len(t):
            return True
        s = sorted(s)
        t = sorted(t)
        def util(s1, t1):
            for i in range(len(s1)):
                if s1[i] > t1[i]:
                    return False
            return True
        if util(s, t):
            return True
        s, t = t, s
        return util(s, t)

ob = Solution()
s = "vyx"
t = "wzx"
print(ob.solve(s, t))

อินพุต

"vyx", "wzx"

เอาต์พุต

True