Problem statement

https://binarysearch.com/problems/Ambigram-Detection/

Solution

Use union find and then check if we have palindrome.

Complexity

It is O(n) for time and O(26) for space.

Code

class DSU:
    def __init__(self):
        self.p = {x:x for x in "abcdefghijklmonpqrstuvwxyz"}

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def solve(self, s, pairs):
        dsu = DSU()
        for x, y in pairs:
            dsu.union(x, y)

        for x, y in zip(s, s[::-1]):
            if dsu.find(x) != dsu.find(y): return False
        
        return True