[Leetcode] 1061. Lexicographically Smallest Equivalent String

문제

 

https://leetcode.com/problems/lexicographically-smallest-equivalent-string/description/

Lexicographically Smallest Equivalent String - LeetCode

You are given two strings of the same length s1 and s2 and a string baseStr.

We say s1[i] and s2[i] are equivalent characters.

• For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

• Reflexivity: 'a' == 'a'.
• Symmetry: 'a' == 'b' implies 'b' == 'a'.
• Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

 

Example 1:

Input	Output
s1 = "parker", s2 = "morris", baseStr = "parser"	"makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is "makkek".

 

Example 2:

Input	Output
s1 = "hello", s2 = "world", baseStr = "hold"	"hdld"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".

 

Example 3:

Input	Output
s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"	"aauaaaaada"
Explanation: We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".

 

Constraints:

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• s1, s2, and baseStr consist of lowercase English letters.

 

 

문제풀이 코드

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        UF = {}

        def find(x):
            if x not in UF:
                UF[x] = x
            
            if x != UF[x]:
                print(x, UF[x])
                UF[x] = find(UF[x])
            return UF[x]
                

        def union(x, y):
            # 두 값의 루트값을 탐색
            rootX = find(x)
            rootY = find(y)
			
            # 두 루트값 중 더 작은 값을 루트노드로 초기화한다
            if rootX > rootY:
                UF[rootX] = rootY
            else:
                UF[rootY] = rootX
        
        for i in range(len(s1)):
            union(s1[i], s2[i])
        
        answer = ""
        for s in baseStr:
            answer += find(s)
        return answer

풀이방식: 서로 연결된 알파벳들은 연결된 알파벳 중 가장 작은 알파벳으로 루트값을 가져가야 하기 때문에 Union-Find 알고리즘 사용

 

1. 기본적인 Union-Find 알고리즘을 구현한다

  - union: 두 값의 루트 값을 찾아 둘 중 더 작은 값을 가지는 루트값으로 루트노드를 바꿔준다.

  - find: 재귀 함수를 통해 현재 값의 루트값을 찾는다.

2. union 함수에 s1[i]와 s2[i]를 파라미터로 넣어 호출한다.(s1[i]와 s2[i]는 같은 집합)

3. 반복문이 종료되면 UF는 같은 집합끼리 묶여 그 집합내에 가장 작은 값을 루트노드로 가지게 된다.

4. baseStr의 문자들과 연결되는 값을 find함수를 통해 찾아온다.