algorithm - 使一个给定的字谜与另一个字谜所需的最小交换次数

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
给定两个anagrams s1和s2，我们希望将s1 anagram转换为s2 anagram。我们需要找出这需要的相邻交换的最小数量。
例如：s1:cat和s2:act。这里交换的最小数量只有1。把C换成A得到S2。
我们怎么能用动态规划来做。有可能吗？

最佳答案

获得最优解的一种方法是将问题减少到shortest path problem。
在这里，每个顶点是使用给定字母的一个可能的anagram两个顶点之间的边（ANGRAM）存在，当且仅当你可以用一个交换从一个移动到另一个时。
找到从输入anagram到所需anagram的最短路径将为您提供最佳路径数。
未加权图的最短路径问题可以用BFS、bi-directionalbfs或A* algorithm来解决。