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^4
  • 1 <= messages[i].length <= 100
  • 1 <= senders[i].length <= 10
  • messages[i] 由大写和小写英文字母及空格组成
  • messages[i] 中的所有单词由单个空格分隔
  • messages[i] 没有前导或尾随空格
  • senders[i] 仅由大写和小写英文字母组成

解题思路

解题思路

这道题需要统计每个发送者的总单词数，然后找出单词数最多的发送者。如果有并列，则返回字典序最大的。

核心思路：

  1. 统计单词数：对于每条消息，计算其包含的单词数量。一个简单的方法是统计空格数量然后加1，因为n个单词之间有n-1个空格
  2. 哈希表累计：使用哈希表记录每个发送者的累计单词数
  3. 找出最优解：遍历哈希表，找出单词数最多的发送者。如果单词数相同，选择字典序更大的

实现细节：

  • 可以通过计算消息中空格的数量来确定单词数：单词数 = 空格数 + 1
  • 也可以直接按空格分割字符串，然后计算分割后数组的长度
  • 在比较发送者时，需要同时考虑单词数和字典序

时间复杂度优化：

使用哈希表可以在一次遍历中完成统计和查找，整体时间复杂度为O(n*m)，其中n是消息数量，m是消息的平均长度。

代码实现

class Solution {
public:
    string largestWordCount(vector<string>& messages, vector<string>& senders) {
        unordered_map<string, int> wordCount;
        
        // 统计每个发送者的单词数
        for (int i = 0; i < messages.size(); i++) {
            int words = count(messages[i].begin(), messages[i].end(), ' ') + 1;
            wordCount[senders[i]] += words;
        }
        
        // 找出单词数最多的发送者
        string result;
        int maxCount = 0;
        
        for (auto& [sender, count] : wordCount) {
            if (count > maxCount || (count == maxCount && sender > result)) {
                maxCount = count;
                result = sender;
            }
        }
        
        return result;
    }
};

class Solution:
    def largestWordCount(self, messages: List[str], senders: List[str]) -> str:
        word_count = {}
        
        # 统计每个发送者的单词数
        for message, sender in zip(messages, senders):
            words = message.count(' ') + 1
            word_count[sender] = word_count.get(sender, 0) + words
        
        # 找出单词数最多的发送者
        result = ""
        max_count = 0
        
        for sender, count in word_count.items():
            if count > max_count or (count == max_count and sender > result):
                max_count = count
                result = sender
        
        return result

public class Solution {
    public string LargestWordCount(string[] messages, string[] senders) {
        Dictionary<string, int> wordCount = new Dictionary<string, int>();
        
        // 统计每个发送者的单词数
        for (int i = 0; i < messages.Length; i++) {
            int words = messages[i].Count(c => c == ' ') + 1;
            if (wordCount.ContainsKey(senders[i])) {
                wordCount[senders[i]] += words;
            } else {
                wordCount[senders[i]] = words;
            }
        }
        
        // 找出单词数最多的发送者
        string result = "";
        int maxCount = 0;
        
        foreach (var kvp in wordCount) {
            if (kvp.Value > maxCount || 
                (kvp.Value == maxCount && string.Compare(kvp.Key, result) > 0)) {
                maxCount = kvp.Value;
                result = kvp.Key;
            }
        }
        
        return result;
    }
}

/**
 * @param {string[]} messages
 * @param {string[]} senders
 * @return {string}
 */
var largestWordCount = function(messages, senders) {
    const wordCount = {};
    
    for (let i = 0; i < messages.length; i++) {
        const count = messages[i].split(' ').length;
        wordCount[senders[i]] = (wordCount[senders[i]] || 0) + count;
    }
    
    let maxCount = 0;
    let result = "";
    
    for (const sender in wordCount) {
        if (wordCount[sender] > maxCount || 
            (wordCount[sender] === maxCount && sender > result)) {
            maxCount = wordCount[sender];
            result = sender;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m)，其中 n 是消息数量，m 是消息的平均长度。需要遍历所有消息计算单词数，然后遍历哈希表找最优解
空间复杂度O(k)，其中 k 是不同发送者的数量，用于存储哈希表

相关题目