E3838.带权单词映射

implementation, https://leetcode.cn/problems/weighted-word-mapping/

给你一个字符串数组 words，其中每个字符串表示一个由小写英文字母组成的单词。

同时给你一个长度为 26 的整数数组 weights，其中 weights[i] 表示第 i 个小写英文字母的权重。

单词的权重定义为其所有字符权重的总和。

对于每个单词，将其权重对 26 取模，并将结果按字母倒序映射到一个小写英文字母（0 -> 'z', 1 -> 'y', ..., 25 -> 'a'）。

返回一个由所有单词映射后的字符按顺序连接而成的字符串。

示例 1：

输入： words = ["abcd","def","xyz"], weights = [5,3,12,14,1,2,3,2,10,6,6,9,7,8,7,10,8,9,6,9,9,8,3,7,7,2]

输出： "rij"

解释：

"abcd" 的权重是 5 + 3 + 12 + 14 = 34。对 26 取模的结果是 34 % 26 = 8，映射为 'r'。
"def" 的权重是 14 + 1 + 2 = 17。对 26 取模的结果是 17 % 26 = 17，映射为 'i'。
"xyz" 的权重是 7 + 7 + 2 = 16。对 26 取模的结果是 16 % 26 = 16，映射为 'j'。

因此，连接映射字符后形成的字符串是 "rij"。

示例 2：

输入： words = ["a","b","c"], weights = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

输出： "yyy"

解释：

每个单词的权重均为 1。对 26 取模的结果是 1 % 26 = 1，映射为 'y'。

因此，连接映射字符后形成的字符串是 "yyy"。

示例 3：

输入： words = ["abcd"], weights = [7,5,3,4,3,5,4,9,4,2,2,7,10,2,5,10,6,1,2,2,4,1,3,4,4,5]

输出： "g"

解释：

"abcd" 的权重是 7 + 5 + 3 + 4 = 19。对 26 取模的结果是 19 % 26 = 19，映射为 'g'。

因此，连接映射字符后形成的字符串是 "g"。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 10
weights.length == 26
1 <= weights[i] <= 100
words[i] 仅由小写英文字母组成。

这是一个在 Python 3 中解决“带权单词映射”问题的实现方法。

解题思路

计算单词权重：对于给定的每一个单词 word，遍历其所有字符，根据 weights 数组获取每个字符的权重，并计算总和。由于字符是小写英文字母，字符 c 对应的 weights 索引可以通过 ord(c) - ord('a') 得到。
取模运算：将计算得到的总权重对 26 取模，即 R = weight % 26。
字符映射：根据题目要求的字母倒序映射规则：
- 0 -> 'z'
- 1 -> 'y'
- ...
- 25 -> 'a'
我们可以通过公式 chr(ord('z') - R) 得到映射后的字符。
拼接结果：对 words 中的每一个单词依次处理，将得到的映射字符拼接成一个完整的字符串并返回。

Python 3 实现

python

from typing import List

class Solution:
    def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
        result = []
        ord_a = ord('a')
        ord_z = ord('z')
        
        for word in words:
            # 计算单词的总权重
            total_weight = sum(weights[ord(char) - ord_a] for char in word)
            # 计算对 26 取模的结果
            remainder = total_weight % 26
            # 映射到倒序字母表的对应字符
            mapped_char = chr(ord_z - remainder)
            result.append(mapped_char)
            
        return "".join(result)

复杂度分析

时间复杂度： $O (N \times L)$ ，其中 $N$ 是单词数组 words 的长度（最多 100）， $L$ 是每个单词的最大长度（最多 10）。我们需要遍历每个单词的每个字符来计算权重，因此整体时间复杂度与所有单词字符总数成正比。该算法效率较高，能够快速完成处理。
空间复杂度： $O (N)$ ，用于存储每个单词映射后的字符以及最后生成的返回字符串。

E3838.带权单词映射 ​

E3838.带权单词映射