Hard

题目描述

如果我们可以通过交换 s1 中两个字母的位置恰好 k 次得到与 s2 相等的结果，那么字符串 s1 和 s2 互为 k 相似的（对于某些非负整数 k）。

给你两个字母异位词 s1 和 s2，返回 s1 和 s2 的最小 k 值，使得 s1 和 s2 是 k 相似的。

示例 1：

输入：s1 = "ab", s2 = "ba"
输出：1
解释：两个字符串是 1 相似的，因为我们可以用一次交换将 s1 变为 s2："ab" --> "ba"。

示例 2：

输入：s1 = "abc", s2 = "bca"  
输出：2
解释：两个字符串是 2 相似的，因为我们可以用两次交换将 s1 变为 s2："abc" --> "bac" --> "bca"。

提示：

  • 1 <= s1.length <= 20
  • s2.length == s1.length
  • s1 和 s2 只包含集合 {‘a’, ‘b’, ‘c’, ’d’, ’e’, ‘f’} 中的小写字母
  • s2 是 s1 的字母异位词

解题思路

这道题要求找到将字符串 s1 转换为 s2 所需的最少交换次数，是一个典型的最短路径问题，可以用 BFS 解决。

核心思路：

  1. BFS 状态空间搜索：将每个字符串状态看作图中的节点，通过交换操作连接相邻节点，找到从 s1 到 s2 的最短路径。

  2. 剪枝优化：

    • 首先跳过已经匹配的位置，只处理不匹配的字符
    • 对于当前第一个不匹配的位置 i，只考虑与位置 i 后面能形成"双向匹配"的位置进行交换
    • 双向匹配指：s1[i] == s2[j] 且 s1[j] == s2[i]，这样一次交换能同时修正两个位置

  3. 贪心策略：优先选择能够同时修正两个位置的交换，这样能更快收敛到目标状态。

  4. 去重：使用哈希集合记录访问过的状态，避免重复计算。

算法流程：

  • 使用 BFS，队列存储当前字符串状态和已用交换次数
  • 对于每个状态，找到第一个不匹配位置，尝试所有可能的交换
  • 优先选择双向匹配的交换，其次选择单向匹配
  • 当找到目标字符串 s2 时，返回交换次数

代码实现

class Solution {
public:
    int kSimilarity(string s1, string s2) {
        if (s1 == s2) return 0;
        
        queue<pair<string, int>> q;
        unordered_set<string> visited;
        
        q.push({s1, 0});
        visited.insert(s1);
        
        while (!q.empty()) {
            auto [curr, steps] = q.front();
            q.pop();
            
            // 找到第一个不匹配的位置
            int i = 0;
            while (i < curr.length() && curr[i] == s2[i]) {
                i++;
            }
            
            // 尝试交换
            for (int j = i + 1; j < curr.length(); j++) {
                if (curr[j] == s2[i]) {
                    swap(curr[i], curr[j]);
                    
                    if (curr == s2) {
                        return steps + 1;
                    }
                    
                    if (visited.find(curr) == visited.end()) {
                        visited.insert(curr);
                        q.push({curr, steps + 1});
                    }
                    
                    swap(curr[i], curr[j]); // 回溯
                    
                    // 贪心：如果找到双向匹配，优先处理
                    if (curr[i] == s2[j]) {
                        break;
                    }
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        if s1 == s2:
            return 0
        
        queue = deque([(s1, 0)])
        visited = {s1}
        
        while queue:
            curr, steps = queue.popleft()
            
            # 找到第一个不匹配的位置
            i = 0
            while i < len(curr) and curr[i] == s2[i]:
                i += 1
            
            # 尝试交换
            for j in range(i + 1, len(curr)):
                if curr[j] == s2[i]:
                    # 执行交换
                    curr_list = list(curr)
                    curr_list[i], curr_list[j] = curr_list[j], curr_list[i]
                    next_state = ''.join(curr_list)
                    
                    if next_state == s2:
                        return steps + 1
                    
                    if next_state not in visited:
                        visited.add(next_state)
                        queue.append((next_state, steps + 1))
                    
                    # 贪心：如果找到双向匹配，优先处理
                    if curr[i] == s2[j]:
                        break
        
        return -1

public class Solution {
    public int KSimilarity(string s1, string s2) {
        if (s1 == s2) return 0;
        
        Queue<(string, int)> queue = new Queue<(string, int)>();
        HashSet<string> visited = new HashSet<string>();
        
        queue.Enqueue((s1, 0));
        visited.Add(s1);
        
        while (queue.Count > 0) {
            var (curr, steps) = queue.Dequeue();
            
            // 找到第一个不匹配的位置
            int i = 0;
            while (i < curr.Length && curr[i] == s2[i]) {
                i++;
            }
            
            // 尝试交换
            for (int j = i + 1; j < curr.Length; j++) {
                if (curr[j] == s2[i]) {
                    // 执行交换
                    char[] chars = curr.ToCharArray();
                    (chars[i], chars[j]) = (chars[j], chars[i]);
                    string nextState = new string(chars);
                    
                    if (nextState == s2) {
                        return steps + 1;
                    }
                    
                    if (!visited.Contains(nextState)) {
                        visited.Add(nextState);
                        queue.Enqueue((nextState, steps + 1));
                    }
                    
                    // 贪心：如果找到双向匹配，优先处理
                    if (curr[i] == s2[j]) {
                        break;
                    }
                }
            }
        }
        
        return -1;
    }
}

var kSimilarity = function(s1, s2) {
    if (s1 === s2) return 0;
    
    const queue = [[s1, 0]];
    const visited = new Set([s1]);
    
    while (queue.length > 0) {
        const [current, swaps] = queue.shift();
        
        // Find first position where characters differ
        let i = 0;
        while (i < current.length && current[i] === s2[i]) {
            i++;
        }
        
        // Try swapping with all valid positions
        for (let j = i + 1; j < current.length; j++) {
            if (current[j] === s2[i]) {
                const arr = current.split('');
                [arr[i], arr[j]] = [arr[j], arr[i]];
                const newStr = arr.join('');
                
                if (newStr === s2) return swaps + 1;
                
                if (!visited.has(newStr)) {
                    visited.add(newStr);
                    queue.push([newStr, swaps + 1]);
                }
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(N! × N)，其中 N 是字符串长度。最坏情况下需要遍历所有可能的字符串排列，每次状态转换需要 O(N) 时间
空间复杂度O(N! × N)，需要存储访问过的状态，最多有 N! 个不同状态，每个状态占用 O(N) 空间

相关题目