854 K-Similar Strings

854. K-Similar Strings

1. Question

Strings AandBareK-similar (for some non-negative integerK) if we can swap the positions of two letters inAexactlyK times so that the resulting string equalsB.

Given two anagramsAandB, return the smallestK for whichAandBareK-similar.

Example 1:

Input: A = "ab", B = "ba"
Output: 1

Example 2:

Input: A = "abc", B = "bca"
Output: 2

Example 3:

Input: A = "abac", B = "baca"
Output: 2

Example 4:

Input: A = "aabc", B = "abca"
Output: 2

Note:

1. 1 <= A.length == B.length <= 20

2. AandBcontain only lowercase letters from the set{'a', 'b', 'c', 'd', 'e', 'f'}

2. Implementation

(1) BFS

class Solution {
    public int kSimilarity(String A, String B) {
        if (A.equals(B)) {
            return 0;
        }
        
        Queue<String> queue = new LinkedList();
        queue.add(A);
        
        Set<String> visited = new HashSet();
        visited.add(A);
        
        int swap = 0;
        while (!queue.isEmpty()) {
            ++swap;
            int size = queue.size();
            
            while (size-- > 0) {
                String curStr = queue.remove();
                int i = 0;
                
                while (curStr.charAt(i) == B.charAt(i)) ++i;
                
                for (int j = i + 1; j < A.length(); j++) {
                    if (curStr.charAt(j) == B.charAt(j) || curStr.charAt(i) != B.charAt(j)) continue;
                    
                    String nextStr = swap(curStr, i, j);
                    
                    if (nextStr.equals(B)) {
                        return swap;
                    }
                    
                    if (visited.add(nextStr)) {
                        queue.add(nextStr);
                    }
                }
            }
        }
        return -1;
    }
    
    public String swap(String s, int i, int j) {
        char[] letters = s.toCharArray();
        char temp = letters[i];
        letters[i] = letters[j];
        letters[j] = temp;
        return new String(letters);
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(n^2), 空间复杂度O(n)