# 854 K-Similar Strings

## 854. [K-Similar Strings](https://leetcode.com/problems/k-similar-strings/description/)

## 1. Question

Strings `A`and`B`are`K`-similar (for some non-negative integer`K`) if we can swap the positions of two letters in`A`exactly`K` times so that the resulting string equals`B`.

Given two anagrams`A`and`B`, return the smallest`K` for which`A`and`B`are`K`-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. `A`and`B`contain only lowercase letters from the set`{'a', 'b', 'c', 'd', 'e', 'f'}`

## 2. Implementation

**(1) BFS**

```java
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)
