Leetcode 1061 - Lexicographically Smallest Equivalent String

題目

Problem#

給你兩個字串 s1 和 s2 還有一個 baseStr，其中 s1[i] 和 s2[i] 是 equivalent characters，今天給你 baseStr 問你如果用 equivalence relation 替換掉字母後，字典序最小的字串為何?

• Equivalence relation:
  • Reflexivity: 'a' == 'a'
  • Symmetry: 'a' == 'b' $\rightarrow$ 'b' == 'a'
  • Transitivity: 'a' == 'b', 'b' == 'c' 代表 'a' == 'c'

想法#

s1[i] == s2[i] 代表 s1[i] 和 s2[i] 是同一組的，維護分組的資料結構，同時遍歷 s1 和 s2 儲存組資訊，接著遍歷一次 baseStr 去找最小字典序的字元即可(利用剛剛維護的資料結構去查詢同組)

• 時間複雜度: $\mathcal{O}(26(n+m))$
  • n = s1.size()
  • m = baseStr.size()
  • 26 = a ~ z
• 空間複雜度: $\mathcal{O}(26)$

AC Code#