Medium

题目描述

给定两个字符串 s 和 t，你的目标是在 k 步内将 s 转换为 t。

在第 i 步（1 <= i <= k）中，你可以：

  • 从 s 中选择任意一个索引 j（1-indexed），满足 1 <= j <= s.length 且 j 在之前的步骤中没有被选择过，然后将该索引处的字符移位 i 次。
  • 什么也不做。

移位字符意味着用字母表中的下一个字母替换它（循环方式，所以 ‘z’ 变成 ‘a’）。将字符移位 i 次意味着应用移位操作 i 次。

记住任何索引 j 最多只能选择一次。

如果可以在不超过 k 步内将 s 转换为 t，则返回 true，否则返回 false。

示例 1：

输入：s = "input", t = "ouput", k = 9
输出：true
解释：在第6步中，我们将 'i' 移位6次得到 'o'。在第7步中，我们将 'n' 移位1次得到 'u'。

示例 2：

输入：s = "abc", t = "bcd", k = 10
输出：false
解释：我们需要将s中的每个字符移位一次来转换为t。我们可以在第1步中将 'a' 移位到 'b'。但是，无法在剩余的步骤中移位其他字符来从s得到t。

示例 3：

输入：s = "aab", t = "bbb", k = 27
输出：true
解释：在第1步中，我们将第一个 'a' 移位1次得到 'b'。在第27步中，我们将第二个 'a' 移位27次得到 'b'。

约束条件：

  • 1 <= s.length, t.length <= 10^5
  • 0 <= k <= 10^9
  • s, t 只包含小写英文字母。

提示：

  • 观察移位字母x次与移位字母x+26次具有相同效果。
  • 你需要检查k是否足够大，以覆盖所有具有相同模26余数的移位。

解题思路

这道题的关键在于理解移位操作的本质和约束条件。

核心观察：

  1. 每个位置最多只能操作一次，且在第i步操作时移位i次
  2. 移位操作是循环的，移位26次等于移位0次
  3. 如果某个字符需要移位d次才能变成目标字符，那么它可以在第d步、第d+26步、第d+52步等任意一个满足step % 26 == d的步骤中完成

解题思路：

  1. 首先检查两个字符串长度是否相等，不等则直接返回false
  2. 计算每个位置需要的移位距离，统计每种移位距离（mod 26后的值）需要的次数
  3. 对于需要移位d次的字符，第一个可以在第d步完成，第二个在第d+26步，第n个在第d+26*(n-1)步
  4. 检查所有需要的步数是否都不超过k

算法流程： 使用哈希表记录每种移位距离的出现次数，然后验证是否能在k步内完成所有必要的移位操作。

时间复杂度O(n)，空间复杂度O(1)，其中n是字符串长度。

代码实现

class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        if (s.length() != t.length()) {
            return false;
        }
        
        vector<int> count(26, 0);
        
        for (int i = 0; i < s.length(); i++) {
            int shift = (t[i] - s[i] + 26) % 26;
            if (shift != 0) {
                count[shift]++;
            }
        }
        
        for (int i = 1; i < 26; i++) {
            if (count[i] > 0) {
                int maxStep = i + 26 * (count[i] - 1);
                if (maxStep > k) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        count = [0] * 26
        
        for i in range(len(s)):
            shift = (ord(t[i]) - ord(s[i])) % 26
            if shift != 0:
                count[shift] += 1
        
        for i in range(1, 26):
            if count[i] > 0:
                max_step = i + 26 * (count[i] - 1)
                if max_step > k:
                    return False
        
        return True

public class Solution {
    public bool CanConvertString(string s, string t, int k) {
        if (s.Length != t.Length) {
            return false;
        }
        
        int[] count = new int[26];
        
        for (int i = 0; i < s.Length; i++) {
            int shift = (t[i] - s[i] + 26) % 26;
            if (shift != 0) {
                count[shift]++;
            }
        }
        
        for (int i = 1; i < 26; i++) {
            if (count[i] > 0) {
                int maxStep = i + 26 * (count[i] - 1);
                if (maxStep > k) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

var canConvertString = function(s, t, k) {
    if (s.length !== t.length) {
        return false;
    }
    
    const count = new Array(26).fill(0);
    
    for (let i = 0; i < s.length; i++) {
        const shift = (t.charCodeAt(i) - s.charCodeAt(i) + 26) % 26;
        if (shift !== 0) {
            count[shift]++;
        }
    }
    
    for (let i = 1; i < 26; i++) {
        if (count[i] > 0) {
            const maxStep = i + 26 * (count[i] - 1);
            if (maxStep > k) {
                return false;
            }
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。我们只需要遍历一次字符串来统计移位需求，然后检查26种可能的移位距离，因此时间复杂度是线性的。空间复杂度是常数级别，因为我们只使用了固定大小的计数数组。

相关题目