การแปลงสตริงหนึ่งเป็นอีกสตริงหนึ่ง (String Transforms) ใน Python

สมมติว่าเรามีสตริงสองตัว str1 และ str2 ความยาวเท่ากัน เราต้องตรวจสอบว่าแปลง str1 เป็น str2 ได้หรือไม่ โดยทำการแปลงศูนย์ครั้งขึ้นไป

ในหนึ่งครั้งของการแปลง เราสามารถแปลงทุกครั้งของตัวอักษรหนึ่งใน str1 ให้กลายเป็นตัวอักษรภาษาอังกฤษพิมพ์เล็กอีกตัวหนึ่งได้ เราต้องตรวจสอบว่าสามารถแปลงได้หรือไม่

เช่น str1 = "aabcc", str2 = "ccdee" ผลลัพธ์คือ true เพราะ แปลง 'c' เป็น 'e' แล้ว 'b' เป็น 'd' แล้ว 'a' เป็น 'c' ลำดับการแปลงมีความสำคัญ

วิธีแก้ปัญหา (อัลกอริทึมที่ซับซ้อน ใช้การบีบอัดสตริงและตรวจสอบเงื่อนไข):

• ฟังก์ชัน compress(s): บีบอัดสตริงเป็นลิสต์จำนวนตัวอักษรติดกัน

• ฟังก์ชัน canConvert(str1, str2): เปรียบเทียบรูปแบบที่บีบอัดแล้ว และตรวจสอบชุดตัวอักษรใน str2

ตัวอย่างการใช้งาน

class Solution(object):
    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 i in str2:
            if i not in d:
                d[i] = 1
        return True if (26 - len(d)) or str1 == str2 else False

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

อินพุท

"aabcc", "ccdee"

เอาต์พุท

True