Easy

题目描述

给你一个字符串 s 和一个整数 k。使用以下算法加密字符串：

  • 对于 s 中的每个字符 c，将 c 替换为字符串中 c 后面第 k 个字符（以循环方式）。

返回加密后的字符串。

示例 1：

输入：s = "dart", k = 3
输出："tdar"
解释：
- 对于 i = 0，'d' 后面第 3 个字符是 't'。
- 对于 i = 1，'a' 后面第 3 个字符是 'd'。
- 对于 i = 2，'r' 后面第 3 个字符是 'a'。
- 对于 i = 3，'t' 后面第 3 个字符是 'r'。

示例 2：

输入：s = "aaa", k = 1
输出："aaa"
解释：由于所有字符都相同，加密后的字符串也相同。

约束条件：

  • 1 <= s.length <= 100
  • 1 <= k <= 10^4
  • s 仅由小写英文字母组成。

提示：

  • 构造一个新字符串，使得对于 s 中的每个字符，字符 i 对应原字符串中的第 (i + k) % s.length 个字符。

解题思路

这是一个简单的字符串加密问题，核心思想是通过循环移位来实现字符替换。

解题思路：

  1. 理解题意：对于字符串中位置为 i 的字符，我们需要找到它"后面第 k 个"字符来替换它。这里的"后面"是循环的，即到达字符串末尾后会回到开头。

  2. 数学建模：位置 i 的字符应该被位置 (i + k) % n 的字符替换，其中 n 是字符串长度。使用取模运算可以自然地处理循环。

  3. 算法步骤：

    • 创建一个新的字符串或字符数组
    • 遍历原字符串的每个位置 i
    • 计算目标位置 (i + k) % n
    • 将目标位置的字符放入结果字符串的位置 i

  4. 优化考虑：由于 k 可能很大，我们可以先对 k 取模 k % n，减少不必要的循环次数。

这个解法时间复杂度为 O(n)，空间复杂度为 O(n)，是最优解。

代码实现

class Solution {
public:
    string getEncryptedString(string s, int k) {
        int n = s.length();
        k = k % n;  // 优化：减少不必要的循环
        string result(n, ' ');
        
        for (int i = 0; i < n; i++) {
            result[i] = s[(i + k) % n];
        }
        
        return result;
    }
};

class Solution:
    def getEncryptedString(self, s: str, k: int) -> str:
        n = len(s)
        k = k % n  # 优化：减少不必要的循环
        result = []
        
        for i in range(n):
            result.append(s[(i + k) % n])
        
        return ''.join(result)

public class Solution {
    public string GetEncryptedString(string s, int k) {
        int n = s.Length;
        k = k % n;  // 优化：减少不必要的循环
        char[] result = new char[n];
        
        for (int i = 0; i < n; i++) {
            result[i] = s[(i + k) % n];
        }
        
        return new string(result);
    }
}

var getEncryptedString = function(s, k) {
    const n = s.length;
    k = k % n;  // 优化：减少不必要的循环
    let result = '';
    
    for (let i = 0; i < n; i++) {
        result += s[(i + k) % n];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串一次，其中 n 是字符串长度
空间复杂度O(n)需要创建新的结果字符串存储加密结果