最多单词数的发件人

难度: Medium

给你一个聊天记录，共包含 n 条信息。给你两个字符串数组 messages 和 senders ，其中 messages[i] 是 senders[i] 发出的一条信息。

一条信息是若干用单个空格连接的单词，信息开头和结尾不会有多余空格。发件人的 单词计数 是这个发件人总共发出的 单词数 。注意，一个发件人可能会发出多于一条信息。

请你返回发出单词数最多的发件人名字。如果有多个发件人发出最多单词数，请你返回 字典序 最大的名字。

注意：

字典序里，大写字母小于小写字母。
"Alice" 和 "alice" 是不同的名字。

示例 1：

输入：messages = ["Hello userTwooo","Hi userThree","Wonderful day Alice","Nice day userThree"], senders = ["Alice","userTwo","userThree","Alice"]
输出："Alice"
解释：Alice 总共发出了 2 + 3 = 5 个单词。
userTwo 发出了 2 个单词。
userThree 发出了 3 个单词。
由于 Alice 发出单词数最多，所以我们返回 "Alice" 。

示例 2：

输入：messages = ["How is leetcode for everyone","Leetcode is useful for practice"], senders = ["Bob","Charlie"]
输出："Charlie"
解释：Bob 总共发出了 5 个单词。
Charlie 总共发出了 5 个单词。
由于最多单词数打平，返回字典序最大的名字，也就是 Charlie 。

提示：

n == messages.length == senders.length
1 <= n <= 10⁴
1 <= messages[i].length <= 100
1 <= senders[i].length <= 10
messages[i] 包含大写字母、小写字母和 ' ' 。
messages[i] 中所有单词都由 单个空格 隔开。
messages[i] 不包含前导和后缀空格。
senders[i] 只包含大写英文字母和小写英文字母。

Submission

运行时间: 63 ms

内存: 21.8 MB

class Solution:
    def largestWordCount(self, messages: List[str], senders: List[str]) -> str:
        word_count = {}
        
        for message, sender in zip(messages, senders):
            words = message.split()
            word_count[sender] = word_count.get(sender, 0) + len(words)
        
        max_count = max(word_count.values())
        max_senders = [sender for sender, count in word_count.items() if count == max_count]
        
        return max(max_senders)

Explain

首先，本题解的思路是利用一个字典来记录每个发件人发送的单词总数。遍历消息数组和发送者数组，对于每条消息，我们通过split()方法得到消息中单词的数量，并将其累加到对应发件人的计数上。完成遍历后，我们寻找字典中单词计数最大的值，然后再从字典中找出所有单词计数等于最大值的发件人。最后，返回这些发件人中字典序最大的一个。

时间复杂度: O(n*m)

空间复杂度: O(n)

class Solution:
    def largestWordCount(self, messages: List[str], senders: List[str]) -> str:
        word_count = {}  # 创建字典存储每个发件人的单词计数
        
        for message, sender in zip(messages, senders):
            words = message.split()  # 分割每条消息的单词
            word_count[sender] = word_count.get(sender, 0) + len(words)  # 更新发件人的单词计数
        
        max_count = max(word_count.values())  # 找到最大的单词计数
        max_senders = [sender for sender, count in word_count.items() if count == max_count]  # 找出所有单词计数等于最大值的发件人
        
        return max(max_senders)  # 返回字典序最大的发件人

Explore

字典（或哈希表）在此类问题中被广泛使用主要是因为其高效的查找、插入和更新操作。字典允许以常数时间复杂度（平均情况）进行这些操作，这使得在处理大量数据时，能够快速地更新和查询每个发送者的单词计数。相比之下，如果使用列表或数组，每次更新或检索都可能需要线性时间，这在数据量大时效率较低。

Python的split()方法默认会以空白字符（包括空格、换行符等）作为分隔符，并且会忽略字符串开始和结束的空白字符。当遇到连续的空白字符时，split()会将它们视为单个分隔符，因此可以正确计数单词，不会因连续空格而增加计数。但是，split()默认不会处理特殊字符，特殊字符如标点符号会被视为单词的一部分，除非显式指定分隔符。

使用字典的get方法可以更简洁高效地处理键不存在的情况。get方法允许在键不存在时返回一个默认值，这里是0，这样可以直接进行累加操作，避免了先检查键是否存在再决定是插入新键还是更新现有键的步骤。若直接判断键是否存在，代码会更长，且可能涉及两次键访问（一次检查，一次更新），这在某些情况下会略微降低效率。

通过首先获取所有单词计数等于最大值的发件人列表，然后使用Python内置的max函数，可以直接找出这些发件人中字典序最大的一个。max函数在比较字符串时会按字典序进行比较，因此能够确保在有多个发件人的单词数量相同时，返回的是字典序最大的名字。