2023-01-14.md

题目

1061. Lexicographically Smallest Equivalent String

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.

思路

用parent[c]记录c的最小等价字符 需要注意baseStr中的字符有可能不在s1和s2中

代码

var smallestEquivalentString = function(s1, s2, baseStr) {
  const parent = {}
  for (let i = 0; i < s1.length; i++) {
    parent[s1[i]] = s1[i]
    parent[s2[i]] = s2[i]
  }
  function findParent(character) {
    let c = character
    while(parent[c] != c) {
      c = parent[c]
    }
    parent[character] = c
    return c
  }
  for (let i = 0; i < s1.length; i++) {
    const p1 = findParent(s1[i])
    const p2 = findParent(s2[i])
    const smallerParent = p1 < p2 ? p1 : p2
    parent[parent[s1[i]]] = smallerParent
    parent[parent[s2[i]]] = smallerParent
    parent[s1[i]] = smallerParent
    parent[s2[i]] = smallerParent
  }
  let result = ''
  for (let i = 0; i < baseStr.length; i++) {
    const p = findParent(baseStr[i])
    if (p) {
      result += p
    } else {
      result += baseStr[i]
    }
  }
  return result
}