思路1 并查集

首先明确说明是汉明距离:

  • 相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量

如果allowedSwaps有[1,2]和[2,3],那么[1,3]也是可以交换的。

这道题变可以转换成用并查集找连通分量。一个连通分量内所有下表都是可以交换的。

最后每个连通分量内,source和target不同元素的个数,就是当前连通分量的汉明距离。最后把所有的连通分量的汉明距离加起来就行了

Last updated