854. K-Similar Strings

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

找最短距離的概念常可以用BFS的概念實現，要用到queue來達到BFS然後unordered_set來紀錄已經搜尋過的中間結果。先找到當前這個string和目標string不一樣的char位置i，然後再從這個位置i往後找到位置j使得當前這個string的第j個位置上的char和目標string的第j個位置上的char不一樣，且目標string上的第j個char和當前string的第i個char一樣，就可以swap然後判斷沒搜尋過的話就能加入queue還有hashset中。這就像是一種greedy method找第一個不符合的char然後再找到不符合的char該放到哪。

// BFS
int kSimilarity(string A, string B) {
    if (A == B) return 0;
    int res = 0, len = A.length();
    queue<string> q({A});
    unordered_set<string> visited({A});
    while (!q.empty()) {
        ++res;
        for (int k = q.size() - 1; k >= 0; --k) {
            string str = q.front(); q.pop();
            int i = 0;
            while (str[i] == B[i]) ++i;
            for (int j = i + 1; j < len; ++j) {
                if (str[j] == B[j] || str[i] != B[j]) continue; // Skip already sorted or unmatched 
                swap(str[i], str[j]);
                if (str == B) return res;
                if (!visited.count(str)) {
                    q.push(str);
                    visited.insert(str);
                }
                swap(str[i], str[j]); // reset
            }
        }
    }
    return res;
}

// DFS Backtracking
int backtracking(string& A, const string& B, unordered_map<string, int>& mp, int i) {
    if (A == B) return 0;
    if (mp.count(A)) return mp[A];
    int res = INT_MAX;
    while (i < A.length() && A[i] == B[i]) ++i;
    for (int j = i + 1; j < A.length(); ++j) {
        if (A[j] == B[i]) {
            swap(A[i], A[j]);
            int next = backtracking(A, B, mp, i + 1);
            if (next != INT_MAX) {
                res = min(res, next + 1);
            }
            swap(A[i], A[j]);
        }
    }
    mp[A] = res;
    return res;
}
int kSimilarity(string A, string B) {
    unordered_map<string, int> mp;
    return backtracking(A, B, mp, 0);
}