FB经典面试题型

如果可以通过将 A 中的两个字母精确地交换位置 K 次得到与 B 相等的字符串，我们称字符串 A 和 B 的相似度为 K，给定两个字母异位词 A 和 B ，返回 A 和 B 的相似度 K 的最小值。

例如：
输入：A = "ab", B = "ba"
输出：1、

这个题主要是入手点不好找，要转化成图：我们对字符串 A 和 B 构造一个包含 6 个节点 a, b, c, d, e, f 的基础图,对于字符串中的第 i 位 A[i] 和 B[i]，我们在基础图中连一条 A[i] -> B[i] 的有向边，允许重边和自环。

如果字符串 A 和 B 相等，那么基础图

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我们把基础图 G 拆分为环并进行截断操作时，我们可以每次截断从左到右第一个 A[i] != B[i] 对应的那条边，即在字符串 A 和 B 中，我们每次找到最左侧满足 A[i] != B[i] 的 i，并搜索满足 j > i 且 A[j] == B[i] 的 j。通过这种做法，我们可以使用广度优先搜索遍历所有的状态。