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

    这道题说是当字符串A通过交换自身的字符位置K次能得到字符串B的话,就说字符串A和B的相似度为K。现在给了两个异构词A和B,问最小的相似度是多少。换一种说法就是,最少交换多少次可以将字符串A变为B,在另一道题目 Snakes and Ladders 中提到了求最小值还有一大神器,广度优先搜索 BFS,最直接的应用就是在迷宫遍历的问题中,求从起点到终点的最少步数,也可以用在更 general 的场景,只要是存在确定的状态转移的方式,可能也可以使用。这道题就是更 general 的应用,起点状态就是A,目标状态是B,状态转移的方式就是进行字符交换,博主开始想的是对当前状态遍历所有的交换可能,产生的新状态若不在 visited 集合中就加入队列继续遍历,可是这种 Naive 的思路最终超时了 Time Limit Exceeded。为什么呢?因为对于每个状态都遍历所有都交换可能,则每一个状态都有平方级的复杂度,整个时间复杂度就太大了,虽然有很多重复的状态不会加入队列中,但就算是交换字符,HashSet 查重这些操作也够编译器喝一壶的了。所以必须要进行优化,而且是大幅度的优化。首先来想,为啥要限定A和B是异构词,这表明A和B中的字符的种类及其个数都相同,就是排列顺序不同,则A经过交换是一定能变为B的,而且交换的次数在区间 [0, n-1] 内,n是A的长度。再来想,是不是A中的每个字符都需要交换呢?答案是否定的,当A中某个位置i上的字符和B中对应位置的字符相等,即 A[i]=B[i] 时,就不需要交换,这样就可以用一个 while 循环,找到第一个不相等的i。交换的第一个字符确定了,就可以再往后遍历,去找第二个字符了,同理,第二个字符位置j,不能存在 A[j]=B[j],比如 ab 和 bb,交换之后变为 ba 和 bb,还是不相等,最好是存在 A[j]=B[i],比如 ab 和 ba,这样交换之后就变为 ba 和 ba,完美 match 了。找到了i和j之后,就可以进行交换了,然后判断新状态不在 visited 中的话,加入 visited 集合,同时加入队列 queue,之后还要交换i和j还原状态,每一层遍历结束后,结果 res 自增1即可,参见代码如下:
    解法一:

    class Solution {
    public:
    int kSimilarity(string A, string B) {

       int res = 0, n = A.size();
       queue<string> q{{A}};
       unordered_set<string> visited{{A}};
       while (!q.empty()) {
           for (int k = q.size(); k > 0; --k) {
               string cur = q.front(); q.pop();
               if (cur == B) return res;
               int i = 0;
               while (i < n && cur[i] == B[i]) ++i;
               for (int j = i + 1; j < n; ++j) {
                   if (cur[j] == B[j] || cur[j] != B[i]) continue;
                   swap(cur[i], cur[j]);
                   if (!visited.count(cur)) {
                       visited.insert(cur);
                       q.push(cur);
                   }
                   swap(cur[i], cur[j]);
               }
           }
           ++res;
       }
       return -1;
    

    }
    };

    我们也可以使用递归+记忆数组的方式来写,这里没用数组,而是用的 HashMap,没啥太大区别。在递归函数中,先判断若当前状态 cur 和B相等了,直接返回0,若 cur 已经在 HashMap 中存在了,返回其映射值。之后就进行和上面相同的操作,先找出使得 cur[i] 和 B[i] 不同的i,然后从 i+1 开始遍历j,遇到 cur[j]=B[j] 或 cur[j]!=B[i] 时跳过,交换 cur 中的i和j位置,对新状态调用递归,若返回值不是整型最大值,则将其加1,并更新结果 res,然后恢复 cur 之前的状态。for 循环结束后,在 HashMap 中建立 cur 和结果 res 的映射,并返回映射值即可。注意这里的 for 循环中只能写成 cur[j] != B[i],而上面的解法好像还可以写成 cur[i] != B[j],感觉蛮奇怪的,各位看官大神们知道原因的请留言告诉博主哈~
    解法二:

    class Solution {
    public:
    int kSimilarity(string A, string B) {

       unordered_map<string, int> memo;
       return helper(A, B, 0, memo);
    

    }
    int helper(string cur, string B, int i, unordered_map<string, int>& memo) {

       if (cur == B) return 0;
       if (memo.count(cur)) return memo[cur];
       int res = INT_MAX, n = cur.size();
       while (i < n && cur[i] == B[i]) ++i;
       for (int j = i + 1; j < n; ++j) {
           if (cur[j] == B[j] || cur[j] != B[i]) continue;
           swap(cur[i], cur[j]);
           int next = helper(cur, B, i + 1, memo);
           if (next != INT_MAX) {
               res = min(res, next + 1);
           }
           swap(cur[i], cur[j]);
       }
       return memo[cur] = res;
    

    }
    };

    这道题还有一种基于贪婪算法的神奇递归写法,清新脱俗,击败率也蛮高的。之前提到了由于A和B是异构词,则A经过交换是一定能变为B的,而且交换的次数在区间 [0, n-1] 内,n是A的长度。最好的情况就是一次交换可以产生两个 match,比如 bac 和 abc,通过交换 bac 的前两个字符,直接就变成 abc。所以只要遇到能一次变换产生两个 match 的,一定是最优解的一部分,可以直接对后面剩余部分调用递归并累加。但也有无法产生两个 match 的时候,比如 bac 和 acb,不论如何变换,都没法做到一次交换产生两个 match,那就退而求其次吧,产生1个新的 match 也行,但此时不能直接对其调用递归返回,因为谁知道后面还有没有能产生2个 match 的,所以要把当前的j位置先保存到一个数组中,直到确认了后面都不会有产生2个 match 的位置后,再来处理这些只产生1个 match 的备胎们,方法是取出每个备胎,和i进行交换,然后调用递归,返回加1后来更新结果 res,再交换回来恢复状态。最后返回结果 res 即可,参见代码如下:
    解法三:

    class Solution {
    public:
    int kSimilarity(string A, string B) {

       int n = A.size(), res = n - 1;
       for (int i = 0; i < n; ++i) {
           if (A[i] == B[i]) continue;
           vector<int> matches;
           for (int j = i + 1; j < n; ++j) {
               if (A[j] == B[j] || A[j] != B[i]) continue;
               matches.push_back(j);
               if (A[i] != B[j]) continue;
               swap(A[i], A[j]);
               return 1 + kSimilarity(A.substr(i + 1), B.substr(i + 1));
           }
           for (int j : matches) {
               swap(A[i], A[j]);
               res = min(res, 1 + kSimilarity(A.substr(i + 1), B.substr(i + 1)));
               swap(A[i], A[j]);
           }
           return res;
       }
       return 0;
    

    }
    };

    Github 同步地址:

https://github.com/grandyang/leetcode/issues/854

类似题目:

Couples Holding Hands

参考资料:

https://leetcode.com/problems/k-similar-strings/

https://leetcode.com/problems/k-similar-strings/discuss/140299/C%2B%2B-6ms-Solution

https://leetcode.com/problems/k-similar-strings/discuss/139872/Java-Backtracking-with-Memorization

https://leetcode.com/problems/k-similar-strings/discuss/140099/JAVA-BFS-32-ms-cleanconciseexplanationwhatever

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation