Chương trình kiểm tra tồn tại hoán vị làm cho một chuỗi ≤ chuỗi khác theo thứ tự từ điển trong Python

Mô tả bài toán

Cho hai chuỗi s và t cùng độ dài. Kiểm tra xem có tồn tại hoán vị s1 của s và t1 của t sao cho: hoặc s1[i] ≤ t1[i] cho mọi i, hoặc t1[i] ≤ s1[i] cho mọi i.

Ví dụ: s = "vyx", t = "wzx" → True (hoán vị thành s1="vxy", t1="wxz").

Giải thuật (Sắp xếp + So sánh)

1. Nếu một chuỗi rỗng: trả về True.
2. Sắp xếp cả hai chuỗi.
3. Định nghĩa hàm util(s1, t1): kiểm tra s1[i] ≤ t1[i] ∀i.
4. Nếu util(s, t) đúng: trả về True.
5. Ngược lại hoán đổi s và t, kiểm tra util(s, t).

Ví dụ mã Python

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

Đầu vào

"vyx", "wzx"

Đầu ra

True