Cadena Equivalente Lexicográficamente más Pequeña
Se te dan dos cadenas de la misma longitud s1 y s2 y una cadena baseStr.
Decimos que s1[i] y s2[i] son caracteres equivalentes.
- Por ejemplo, si
s1 = "abc"ys2 = "cde", entonces tenemos'a' == 'c','b' == 'd'y'c' == 'e'.
Los caracteres equivalentes siguen las reglas usuales de cualquier relación de equivalencia:
- Reflexividad:
'a' == 'a' - Simetría:
'a' == 'b'implica'b' == 'a' - Transitividad:
'a' == 'b'y'b' == 'c'implica'a' == 'c'
Por ejemplo, dada la información de equivalencia de s1 = "abc" y s2 = "cde", "acd" y "aab" son cadenas equivalentes de baseStr = "eed", y "aab" es la cadena equivalente lexicográficamente más pequeña de baseStr.
Devuelve la cadena equivalente lexicográficamente más pequeña de baseStr usando la información de equivalencia de s1 y s2.
Ejemplos
Ejemplo 1:
Input: s1 = "parker", s2 = "morris", baseStr = "parser" Output: "makkek" Explicación: - Basándose en la información de equivalencia en s1 y s2, podemos agrupar sus caracteres como [m,p], [a,o], [k,r,s], [e,i]. - Los caracteres en cada grupo son equivalentes y están ordenados lexicográficamente. - Por lo tanto, la respuesta es "makkek".Ejemplo 2:
Input: s1 = "hello", s2 = "world", baseStr = "hold" Output: "hdld" Explicación: - Basándose en la información de equivalencia en s1 y s2, podemos agrupar sus caracteres como [h,w], [d,e,o], [l,r]. - Por lo tanto, solo la segunda letra 'o' en baseStr se cambia a 'd', la respuesta es "hdld".Ejemplo 3:
Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode" Output: "aauaaaaada" Explicación: - Agrupamos los caracteres equivalentes en s1 y s2 como [a,o,e,r,s,c], [l,p], [g,t] y [d,m]. - Por lo tanto, todas las letras en baseStr excepto 'u' y 'd' se transforman en 'a', la respuesta es "aauaaaaada".Soluciones
Python
class Solution:
def find(self, dsuf, v):
if dsuf[v] == -1:
return v
dsuf[v] = self.find(dsuf, dsuf[v])
return dsuf[v]
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
dsuf = [-1] * 26
# Paso-1: Construir conjuntos equivalentes disjuntos (con el más pequeño en cada conjunto como padre absoluto)
for i in range(len(s1)):
if s1[i] == s2[i]:
continue
px = self.find(dsuf, ord(s1[i]) - ord('a'))
py = self.find(dsuf, ord(s2[i]) - ord('a'))
if px == py:
continue
# Unión por el carácter más pequeño como padre absoluto
if px > py:
dsuf[px] = py
else:
dsuf[py] = px
# Paso-2: Iterar por baseStr y encontrar la cadena equivalente lexicográficamente más pequeña
res = []
for c in baseStr:
parent = self.find(dsuf, ord(c) - ord('a'))
res.append(chr(parent + ord('a')))
return ''.join(res)