UNIST, CSE 3th

2 minute read

1061. Lexicographically Smallest Equivalent String

group을 어떻게 구현할지 고민하게되는 문제였다. 이 문제에서 중요한건 equivalent한 character들을 어떻게 group하는지가 관건이었는데, 처음에는 list와 set을 이용하여 구현하려고 하다가 이 방식으로 구현하면 너무 memory가 overflow 될것 같아서 다른 방식으로, lower letter alphabet 이라는 contradiction을 이용하여 간단하게 O(n) memory만을 이용하여 구현하였다. 아이디어는 간단하다, group_id 라는 개념을 이용하는데 같은 그룹일 경우에 같은 group_id를 가지고 새로운 그룹을 만들어야 할 때 마다 새로운 group_id를 할당하여 그룹의 추가 및 삭제를 비교적으로 자유롭게 할 수 있게 만들었다.

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        n = len(s1)
        group = [-1] * 26
        count = 0

        def index(c):
            return ord(c) - 97

        def re_index(n):
            return chr(n + 97)

        for i in range(n):
            a, b = s1[i], s2[i]
            c, d = group[index(a)], group[index(b)]
            if c >= 0 and d >= 0:
                # add two set 
                for i in range(26):
                    if group[i] == c or group[i] == d:
                        group[i] = count
                count += 1
            elif c >= 0 and d == -1:
                # add 'b' to set c
                group[index(b)] = c
            elif c == -1 and d >= 0:
                # add 'a' to set d
                group[index(a)] = d
            else:
                # add set with 'a', 'b'
                group[index(a)] = count
                group[index(b)] = count
                count += 1

        temp = [99] * count
        for i in range(26):
            num = group[i]
            if num >= 0:
                temp[num] = min(temp[num], i)
        
        res = ''
        # print(group)
        for s in baseStr:
            group_id = group[index(s)]
            if group_id == -1:
                res += s
            else:
                res += re_index(temp[group_id])
                # res += chr(temp[group_id] + 97)
        return res

또다른 Solution, Union and Find

나중에 읽어보면 좋을것 같다. 출처 md2023 link

# UF is a hash map where you can find the root of a group of elements giving an element.
# A key in UF is a element, UF[x] is x's parent.
# If UF[x] == x meaning x is the root of its group.
UF = {}

# Given an element, find the root of the group to which this element belongs.
def find(x):
    # this may be the first time we see x or y, so set itself as the root.
    if x not in UF:
        UF[x] = x
    # If x == UF[x], meaning x is the root of this group.
    # If x != UF[x], we use the find function again on x's parent UF[x] 
    # until we find the root and set it as the parent (value) of x in UF.
    if x != UF[x]:
        UF[x] = find(UF[x])
    return UF[x]

# Given two elements x and y, we know that x and y should be in the same group, 
# this means the group that contains x and the group that contains y 
# should be merged together if they are currently separate groups.
# So we first find the root of x and the root of y using the find function.
# We then set the root of y (rootY) as the root of the root of x (rootX).
def union(x, y):

    rootX = find(x)
    rootY = find(y)
    # set the root of y (rootY) as the root of the root of x (rootX)
    UF[rootX] = rootY

You may also enjoy