854. 相似度为 K 的字符串 BFS

854. 相似度为 K 的字符串

字符串 s1 和 s2 是 k 相似 的(对于某些非负整数 k )，如果我们可以交换 s1 中两个字母的位置正好 k 次，使结果字符串等于 s2 。

给定两个字谜游戏 s1 和 s2 ，返回 s1 和 s2 与 k 相似 的最小 k 。

示例 1：

输入：s1 = "ab", s2 = "ba"
输出：1

示例 2：

输入：s1 = "abc", s2 = "bca"
输出：2

提示：

• 1 <= s1.length <= 20
• s2.length == s1.length
• s1 和 s2  只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母
• s2 是 s1 的一个字谜

做题结果

失败，dfs一直超时，头疼

方法：BFS

1. 起点步数为0，化解为求a变成b的最少步数问题

2. 每次用其中某个相同字符进行填写，挪动到对应位置

3. 找到了直接返回

class Solution {
    public int kSimilarity(String s1, String s2) {
        Queue<String> queue = new LinkedList<>();
        Map<String,Integer> distances = new HashMap<>();
        distances.put(s1,0);
        queue.offer(s1);
        while (!queue.isEmpty()){
            String str = queue.poll();
            int nextStep = distances.get(str)+1;
            for(String next:getNext(str,s2)){
                if(next.equals(s2)) return nextStep;
                if(!distances.containsKey(next)){
                    distances.put(next,nextStep);
                    queue.offer(next);
                }
            }
            
        }
        return 0;
    }
    
    private List<String> getNext(String s,String hope){
        List<String> ans = new ArrayList<>();
        char[] cs1 = s.toCharArray();
        char[] cs2 = hope.toCharArray();
        int n = cs1.length;
        int i = 0;
        while (i<n&&cs1[i]==cs2[i]) ++i;
        
        for(int j = i+1; j < n; j++){
            if(cs1[j]!=cs2[j]&&cs1[j]==cs2[i]){
                swap(cs1,i,j);
                ans.add(new String(cs1));
                swap(cs1,i,j);
            }
        }
        return ans;
    }
    
    private void swap(char[] cs, int i, int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}