854. String BFS with similarity K

854. The similarity is K String

character string  s1  and  s2  yes  k  be similar   Of ( For some nonnegative integers  k ), If we could exchange  s1  The two letters in the are in the right place  k  Time , Make the result string equal to  s2 .

Given two word puzzles  s1  and  s2 , return  s1  and  s2  And  k  be similar   Minimum  k .

Example 1：

 Input ：s1 = "ab", s2 = "ba"
 Output ：1

Example 2：

 Input ：s1 = "abc", s2 = "bca"
 Output ：2

Tips ：

• 1 <= s1.length <= 20
• s2.length == s1.length
• s1  and  s2   Contains only sets  {'a', 'b', 'c', 'd', 'e', 'f'}  Small letters in
• s2  yes  s1  A word puzzle

The result of doing the question

Failure ,dfs All the time , Have a headache

Method ：BFS

1. The starting steps are 0, Resolve for the sake of seeking a become b The minimum number of steps of

2. Fill in one of the same characters each time , Move to the corresponding position

3. Find it and go back

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;
    }
}