854. K-Similar Strings

📋 Đề Bài

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

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

Example 1:

Input: s1 = "ab", s2 = "ba"
Output: 1
Explanation: The two string are 1-similar because we can use one swap to change s1 to s2: "ab" --> "ba".

Example 2:

Input: s1 = "abc", s2 = "bca"
Output: 2
Explanation: The two strings are 2-similar because we can use two swaps to change s1 to s2: "abc" --> "bac" --> "bca".

Constraints:

1 <= s1.length <= 20
s2.length == s1.length
s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.
s2 is an anagram of s1.

🧠 Thuật Toán & Kỹ Thuật

DFS (Tìm kiếm theo chiều sâu)String (Chuỗi)

⏱️ Thời gian O(V+E)

💾 Không gian O(V)

💻 Lời Giải

C++ 0854-k-similar-strings.cpp

class Solution {
private:
    int n;
    string s1, s2;
    
public:
    int dfs(int i) {
        if (i == n) {
            return 0;
        }
        if (s1[i] == s2[i]) {
            return dfs(i + 1);
        }
        int ans = 1e9;
        for (int j = i + 1; j < n; ++j) {
            if (s1[j] == s2[j]) {
                continue;
            }
            swap(s1[i], s1[j]);
            if (s1[i] == s2[i]) {
                ans = min(ans, 1 + dfs(i + 1));
            }
            swap(s1[i], s1[j]);
        }
        return ans;
    }
    int kSimilarity(string s1, string s2) {
        this->s1 = s1;
        this->s2 = s2;
        this->n = s1.size();
        string t1, t2;
        for (int i = 0; i < n; ++i) {
            if (s1[i] == s2[i]) {
                t1 += s1[i];
                t2 += s2[i];
            }
        }
        s1 = t1, s2 = t2;
        return dfs(0);
    }
};