Medium

题目描述

给你长度相等的两个字符串 s1 和 s2，还有一个字符串 baseStr。

我们称 s1[i] 和 s2[i] 是等价字符。

  • 举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么我们有 'a' == 'c'，'b' == 'd'，'c' == 'e'。

等价字符遵循任何等价关系的一般规则：

  • 自反性：'a' == 'a'
  • 对称性：'a' == 'b' 则意味着 'b' == 'a'
  • 传递性：'a' == 'b' 且 'b' == 'c' 则意味着 'a' == 'c'

例如，s1 = "abc" 和 s2 = "cde" 的等价信息情况下，"acd" 和 "aab" 是 baseStr = "eed" 的等价字符串，其中 "aab" 是最小的字典序等价字符串。

返回在利用 s1 和 s2 的等价信息的前提下，baseStr 的字典序最小的等价字符串。

示例 1：

输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 s1 和 s2 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i]。
每组中的字符都是等价的，并按字典顺序排序。
所以答案是 "makkek"。

示例 2：

输入：s1 = "hello", s2 = "world", baseStr = "hold"
输出："hdld"
解释：根据 s1 和 s2 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r]。
所以只有 baseStr 中的第二个字符 'o' 变为 'd'，答案是 "hdld"。

示例 3：

输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
输出："aauaaaaada"
解释：我们将 s1 和 s2 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m]，因此除了 'u' 和 'd' 之外，baseStr 中的所有字母都转换为 'a'，答案是 "aauaaaaada"。

约束条件：

  • 1 <= s1.length, s2.length, baseStr <= 1000
  • s1.length == s2.length
  • s1、s2 和 baseStr 只包含小写英文字母。

解题思路

这道题的核心是处理字符等价关系，要求找到字典序最小的等价字符串。我们可以从以下几个角度来思考：

思路分析

并查集方法（推荐）：

  • 将每个字符的等价关系看作图中的边，相同连通分量中的字符互相等价
  • 使用并查集数据结构来维护字符之间的等价关系
  • 对于每个连通分量，我们需要找到字典序最小的字符作为代表元素
  • 在合并操作时，总是让字典序较小的字符作为根节点

具体实现步骤：

  1. 初始化并查集，每个字符最初指向自己
  2. 遍历 s1 和 s2，对相同位置的字符执行合并操作
  3. 在合并时确保根节点是字典序最小的字符
  4. 最后遍历 baseStr，将每个字符替换为其所在连通分量的最小字符

这种方法的优势在于能够高效处理传递性关系，时间复杂度接近线性。

代码实现

class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        vector<int> parent(26);
        // 初始化并查集
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        
        // 查找根节点
        function<int(int)> find = [&](int x) -> int {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };
        
        // 合并两个字符，保证字典序小的作为根
        auto unite = [&](int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rootX > rootY) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                }
            }
        };
        
        // 建立等价关系
        for (int i = 0; i < s1.length(); i++) {
            unite(s1[i] - 'a', s2[i] - 'a');
        }
        
        // 构造结果字符串
        string result = "";
        for (char c : baseStr) {
            result += (char)('a' + find(c - 'a'));
        }
        
        return result;
    }
};

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        parent = list(range(26))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                if root_x > root_y:
                    parent[root_x] = root_y
                else:
                    parent[root_y] = root_x
        
        # 建立等价关系
        for c1, c2 in zip(s1, s2):
            unite(ord(c1) - ord('a'), ord(c2) - ord('a'))
        
        # 构造结果字符串
        result = []
        for c in baseStr:
            root = find(ord(c) - ord('a'))
            result.append(chr(ord('a') + root))
        
        return ''.join(result)

public class Solution {
    public string SmallestEquivalentString(string s1, string s2, string baseStr) {
        int[] parent = new int[26];
        
        // 初始化并查集
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        void Unite(int x, int y) {
            int rootX = Find(x);
            int rootY = Find(y);
            if (rootX != rootY) {
                if (rootX > rootY) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                }
            }
        }
        
        // 建立等价关系
        for (int i = 0; i < s1.Length; i++) {
            Unite(s1[i] - 'a', s2[i] - 'a');
        }
        
        // 构造结果字符串
        StringBuilder result = new StringBuilder();
        foreach (char c in baseStr) {
            result.Append((char)('a' + Find(c - 'a')));
        }
        
        return result.ToString();
    }
}

var smallestEquivalentString = function(s1, s2, baseStr) {
    const parent = Array.from({length: 26}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function unite(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX !== rootY) {
            if (rootX > rootY) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
            }
        }
    }
    
    // 建立等价关系
    for (let i = 0; i < s1.length; i++) {
        unite(s1.charCodeAt(i) - 97, s2.charCodeAt(i) - 97);
    }
    
    // 构造结果字符串
    let result = '';
    for (const c of baseStr) {
        const root = find(c.charCodeAt(0) - 97);
        result += String.fromCharCode(97 + root);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
整体O((n + m) × α(26)) ≈ O(n + m)O(1)

其中：

  • n 是 s1 和 s2 的长度
  • m 是 baseStr 的长度
  • α 是反阿克曼函数，对于实际问题规模可视为常数
  • 空间复杂度为常数级，因为只用了固定大小的数组存储26个字母的并查集信息

相关题目