题目描述：
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
示例 1：
输入：s1 = "ab", s2 = "ba"
输出：1
示例 2：
输入：s1 = "abc", s2 = "bca"
输出：2
提示：
1 <= s1.length <= 20s2.length == s1.length-
s1和s2只包含集合{'a', 'b', 'c', 'd', 'e', 'f'}中的小写字母 -
s2是s1的一个字母异位词
解法：AStar 算法
什么是AStar算法？
Astar算法是一种图形搜索算法，常用于寻路。它是个以广度优先搜索为基础，集Dijkstra算法与最佳优先(best fit)算法特点于一身的一种算法。
它通过下面这个函数来计算每个节点的优先级，然后选择优先级最高的节点作为下一个待遍历的节点。优先级函数：f(n) = g(n) + h(n)。
其中：
1.g(n) 是节点n距离起点的代价。
2.h(n)是节点距离终点的预计代价，也就是Astar算法的启发函数。
分析这道题目：
由于题目明确了 s1 和s2 互为字母异位词，即必然有解。
可直接根据本题的规则确保Astar的启发函数h(n)：对于两种状态 a 和 b 直接计算出理论最小的转换次数，我们可以先计算出 a 和 b 相同位置上不用的元素个数 ans，由于每次转换最多可以减少两个不同的字符，即理论上最小转换次数为h(n) = (ans + 1) /2 向下取整。
我们可以使用一个Map<String, Integer> map来保存，字符串s1转化为 target 中间字符串时最少使用步数，那么 g(n) = map.get(target)。
通过优先级函数f(n) = g(n) + h(n)，我们可以使用一个小根堆，用来自动排序优先级。
代码：
class Solution {
int n;
String t;
int f(String s) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans += s.charAt(i) != t.charAt(i) ? 1 : 0;
}
return ans + 1 >> 1;
}
public int kSimilarity(String s1, String s2) {
if (s1.equals(s2)) {
return 0;
}
t = s2;
n = s1.length();
Map<String, Integer> map = new HashMap<>();
PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> {
int v1 = f(a), v2 = f(b), d1 = map.get(a), d2 = map.get(b);
return (v1 + d1) - (v2 + d2);
});
map.put(s1, 0);
pq.add(s1);
while (!pq.isEmpty()) {
String poll = pq.poll();
int step = map.get(poll);
char[] cs = poll.toCharArray();
int idx = 0;
while (idx < n && cs[idx] == t.charAt(idx)) {
idx++;
}
for (int i = idx + 1; i < n; i++) {
if (cs[i] == t.charAt(idx) && cs[i] != t.charAt(i)) {
swap(cs, idx, i);
String newStr = String.valueOf(cs);
if (map.containsKey(newStr) && map.get(newStr) <= step + 1) {
continue;
}
if (newStr.equals(t)) {
return step + 1;
}
map.put(newStr, step + 1);
pq.add(newStr);
swap(cs, idx, i);
}
}
}
return -1;
}
void swap(char[] chars, int i, int j) {
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
}
}
