ตรวจสอบว่า String สองตัวเทียบเท่ากันตามเงื่อนไขหรือไม่ด้วย Python

โจทย์: กำหนด String s และ t ขนาดเท่ากัน ตรวจสอบว่า Equivalent หรือไม่ เงื่อนไข:

1. ทั้งสองเท่ากันเลย, หรือ
2. แบ่ง s, t เป็นครึ่งซ้าย-ขวา (s1,s2 และ t1,t2) แล้ว:
   • s1 ≡ t1 และ s2 ≡ t2 (Recursive), หรือ
   • s1 ≡ t2 และ s2 ≡ t1 (Recursive)

ตัวอย่าง

s = "ppqp", t = "pqpp" → True

แบ่ง: s1="pp", s2="qp", t1="pq", t2="pp" → s1=t2

แบ่งต่อ: s21="q", s22="p", t11="p", t12="q" → s21=t12, s22=t11

อัลกอริทึม (Canonical Form)

• ฟังก์ชัน util(s):
  • ถ้าความยาวคี่ → คืน s
  • left = util(ครึ่งซ้าย), right = util(ครึ่งขวา)
  • คืน min(left+right, right+left) (Lexicographically smallest)
• สอง String เทียบเท่ากัน ⟺ util(s) == util(t)

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

def util(s):
    if len(s) & 1 != 0:
        return s
    left = util(s[0:int(len(s) / 2)])
    right = util(s[int(len(s) / 2):len(s)])
    return min(left + right, right + left)

def solve(s, t):
    return util(s) == util(t)

s = "ppqp"
t = "pqpp"
print(solve(s, t))

Input / Output

Input: "ppqp", "pqpp"
Output: True