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'
- Reflexivity:
想法#
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)$