Medium

题目描述

给你一个长度为 n 的字符串 s 和一个整数 k，其中 n 是 k 的倍数。你的任务是将字符串 s 哈希为一个新的字符串 result，其长度为 n / k。

首先，将 s 分成 n / k 个子串，每个子串的长度为 k。然后，将 result 初始化为空字符串。

对于从开头开始的每个子串：

  • 字符的哈希值是该字符在英文字母表中的索引（例如，‘a’ → 0，‘b’ → 1，…，‘z’ → 25）。
  • 计算子串中所有字符的哈希值之和。
  • 找到这个和除以 26 的余数，称为 hashedChar。
  • 确定英文小写字母表中对应于 hashedChar 的字符。
  • 将该字符附加到 result 的末尾。

返回 result。

示例 1：

输入：s = "abcd", k = 2
输出："bf"
解释：
第一个子串："ab"，0 + 1 = 1，1 % 26 = 1，result[0] = 'b'。
第二个子串："cd"，2 + 3 = 5，5 % 26 = 5，result[1] = 'f'。

示例 2：

输入：s = "mxz", k = 3
输出："i"
解释：
唯一的子串："mxz"，12 + 23 + 25 = 60，60 % 26 = 8，result[0] = 'i'。

约束条件：

  • 1 <= k <= 100
  • k <= s.length <= 1000
  • s.length 能被 k 整除。
  • s 只包含小写英文字母。

解题思路

这道题目是一个典型的字符串模拟题，需要按照给定的规则逐步处理字符串。

解题思路：

  1. 字符串分割：将字符串 s 按照长度 k 进行分割，得到 n/k 个子串。

  2. 哈希计算：对于每个子串，计算其所有字符的哈希值之和。字符的哈希值就是字符在字母表中的位置（‘a’ = 0, ‘b’ = 1, …, ‘z’ = 25）。

  3. 取模运算：将哈希值之和对 26 取模，得到结果字符在字母表中的索引。

  4. 字符转换：将索引转换为对应的字符，并追加到结果字符串中。

实现细节：

  • 可以通过 char - 'a' 来获取字符的哈希值
  • 使用 char('a' + hashedChar) 来将索引转换回字符
  • 外层循环控制子串的起始位置，内层循环计算每个子串的哈希值

整个算法的核心就是模拟题目描述的过程，时间复杂度为 O(n)，其中 n 是字符串的长度。

代码实现

class Solution {
public:
    string stringHash(string s, int k) {
        string result = "";
        int n = s.length();
        
        for (int i = 0; i < n; i += k) {
            int hashSum = 0;
            for (int j = i; j < i + k; j++) {
                hashSum += s[j] - 'a';
            }
            int hashedChar = hashSum % 26;
            result += (char)('a' + hashedChar);
        }
        
        return result;
    }
};

class Solution:
    def stringHash(self, s: str, k: int) -> str:
        result = []
        n = len(s)
        
        for i in range(0, n, k):
            hash_sum = 0
            for j in range(i, i + k):
                hash_sum += ord(s[j]) - ord('a')
            hashed_char = hash_sum % 26
            result.append(chr(ord('a') + hashed_char))
        
        return ''.join(result)

public class Solution {
    public string StringHash(string s, int k) {
        StringBuilder result = new StringBuilder();
        int n = s.Length;
        
        for (int i = 0; i < n; i += k) {
            int hashSum = 0;
            for (int j = i; j < i + k; j++) {
                hashSum += s[j] - 'a';
            }
            int hashedChar = hashSum % 26;
            result.Append((char)('a' + hashedChar));
        }
        
        return result.ToString();
    }
}

var stringHash = function(s, k) {
    let result = "";
    const n = s.length;
    
    for (let i = 0; i < n; i += k) {
        let hashSum = 0;
        for (let j = i; j < i + k; j++) {
            hashSum += s.charCodeAt(j) - 97; // 'a'.charCodeAt(0) = 97
        }
        const hashedChar = hashSum % 26;
        result += String.fromCharCode(97 + hashedChar);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
模拟算法O(n)O(n/k)

说明：

  • 时间复杂度：O(n)，其中 n 是字符串的长度。我们需要遍历整个字符串一次。
  • 空间复杂度：O(n/k)，用于存储结果字符串，其长度为 n/k。