Skip to content

Latest commit

 

History

History
195 lines (144 loc) · 5.73 KB

README.md

File metadata and controls

195 lines (144 loc) · 5.73 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1292
第 138 场双周赛 Q2
字符串
模拟

3271. 哈希分割字符串

English Version

题目描述

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

首先，将 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 只含有小写英文字母。

解法

方法一：模拟

我们可以按照题目描述的步骤模拟即可。

遍历字符串 $s$，每次取 $k$ 个字符，计算它们的哈希值之和，记为 $t$，然后对 $t$ 取模 $26$，找到对应的字符，将其添加到结果字符串的末尾。

最后返回结果字符串即可。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。忽略答案字符串的空间消耗，空间复杂度 $O(1)$。

Python3

class Solution:
    def stringHash(self, s: str, k: int) -> str:
        ans = []
        for i in range(0, len(s), k):
            t = 0
            for j in range(i, i + k):
                t += ord(s[j]) - ord("a")
            hashedChar = t % 26
            ans.append(chr(ord("a") + hashedChar))
        return "".join(ans)

Java

class Solution {
    public String stringHash(String s, int k) {
        StringBuilder ans = new StringBuilder();
        int n = s.length();
        for (int i = 0; i < n; i += k) {
            int t = 0;
            for (int j = i; j < i + k; ++j) {
                t += s.charAt(j) - 'a';
            }
            int hashedChar = t % 26;
            ans.append((char) ('a' + hashedChar));
        }
        return ans.toString();
    }
}

C++

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

Go

func stringHash(s string, k int) string {
	n := len(s)
	ans := make([]byte, 0, n/k)

	for i := 0; i < n; i += k {
		t := 0
		for j := i; j < i+k; j++ {
			t += int(s[j] - 'a')
		}
		hashedChar := t % 26
		ans = append(ans, 'a'+byte(hashedChar))
	}

	return string(ans)
}

TypeScript

function stringHash(s: string, k: number): string {
    const ans: string[] = [];
    const n: number = s.length;

    for (let i = 0; i < n; i += k) {
        let t: number = 0;
        for (let j = i; j < i + k; j++) {
            t += s.charCodeAt(j) - 97;
        }
        const hashedChar: number = t % 26;
        ans.push(String.fromCharCode(97 + hashedChar));
    }

    return ans.join('');
}