Leetcode最小等价字符串：递归实现输出不一致排查求助

问题原因分析 #

1. 核心逻辑错误：未同步更新连通分量内所有节点的映射值
   你的DFS逻辑仅在遍历邻居时更新当前节点的map值，但没有对已经处理过的邻居节点进行反向更新。例如，当某个节点后来找到更小的等价字符时，之前已经处理完的同分量节点的映射值不会被同步更新，导致部分节点的映射值不是整个连通分量的最小值。

2. 遍历顺序不确定性放大了逻辑缺陷
   你使用set存储邻接节点，而Python中set的遍历顺序虽在3.7+版本保留插入顺序，但由于构建邻接表时的双向添加操作（referenceMap[s2[i]].add(s1[i])和referenceMap[s1[i]].add(s2[i])），不同字符的邻接集合插入顺序可能导致遍历顺序变化。这种变化会影响DFS的执行路径：

   • 如果先遍历到包含最小字符的分支，当前节点的映射值会被正确设为最小值，后续遍历其他邻居时会同步更新这些邻居的映射值；
   • 如果先遍历到不包含最小字符的分支，这些分支的节点映射值会被设为较大的字符，后续即使当前节点找到最小值，也不会回溯更新已处理的邻居节点，导致这些节点的映射值错误。

修复方案 #

正确的思路是：先找到每个连通分量的所有节点，确定该分量的最小字符，再将分量内所有节点的映射值统一设为这个最小值。修改后的代码如下：

from collections import defaultdict

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        # 构建邻接表
        adj = defaultdict(list)
        for c1, c2 in zip(s1, s2):
            adj[c1].append(c2)
            adj[c2].append(c1)
        
        visited = set()
        char_map = {}
        
        def dfs(node, component):
            if node in visited:
                return
            visited.add(node)
            component.append(node)
            for neighbor in adj[node]:
                dfs(neighbor, component)
        
        # 处理每个连通分量
        for char in adj:
            if char not in visited:
                component = []
                dfs(char, component)
                # 找到分量中的最小字符
                min_char = min(component)
                # 统一设置映射
                for c in component:
                    char_map[c] = min_char
        
        # 生成结果
        res = []
        for c in baseStr:
            res.append(char_map.get(c, c))
        return ''.join(res)

修复说明 #

1. DFS收集连通分量：修改DFS函数，用于收集当前连通分量的所有节点，而不是逐步更新映射值。
2. 统一设置映射：对每个连通分量，找到其中的最小字符，然后将分量内所有节点的映射值都设为这个最小字符，确保所有节点的映射值都是正确的最小值。
3. 移除不必要的OrderedDict：使用普通字典存储邻接表即可，无需OrderedDict，简化代码。

这样修改后，无论邻接节点的遍历顺序如何，每个连通分量的所有节点都会被设置为该分量的最小字符，结果稳定且符合预期。

内容的提问来源于stack exchange，提问作者Kiran Deep