Biến đổi chuỗi thành chuỗi khác trong Python

Cho hai chuỗi str1 và str2 cùng độ dài. Kiểm tra xem có thể biến đổi str1 thành str2 bằng 0 hoặc nhiều phép chuyển đổi không. Mỗi phép chuyển đổi: thay đổi tất cả lần xuất hiện của một ký tự trong str1 thành bất kỳ ký tự chữ thường nào khác. Thứ tự chuyển đổi quan trọng.

Ví dụ: str1="aabcc", str2="ccdee" → True (c→e, b→d, a→c).

Giải thuật

• Hàm compress(s): nén chuỗi thành mảng đếm độ dài các nhóm ký tự liên tiếp giống nhau
• So sánh mảng nén: nếu a[i] > b[i] tại vị trí nào → False
• Kiểm tra số ký tự khác nhau trong str2: nếu < 26 hoặc str1==str2 → True

Ví dụ triển khai

class Solution:
    def compress(self, s):
        n = len(s)
        a = []
        count = 1
        for i in range(1, n):
            if s[i] != s[i-1]:
                a.append(count)
                count = 1
            else:
                count += 1
        a.append(count)
        return a

    def canConvert(self, str1, str2):
        a = self.compress(str1)
        b = self.compress(str2)
        n = len(a)
        m = len(b)
        d = {}
        n = min(n, m)
        i = 0
        while i < n:
            if a[i] > b[i]:
                return False
            i += 1
        for ch in str2:
            if ch not in d:
                d[ch] = 1
        return True if (26 - len(d)) or (str1 == str2) else False

ob = Solution()
print(ob.canConvert("aabcc", "ccdee"))

Đầu vào

"aabcc", "ccdee"

Đầu ra

True