LeetCode 2114简单数组 · 哈希
句子中的最多单词数 图解题解
这道题到底在问什么
给你一个字符串数组 sentences,每个元素是一句话。句子里单词之间正好一个空格,开头结尾没有空格,只含小写字母和空格。返回单个句子里单词的最多数目。
- 输入
- sentences=["i can do it","red fox","go"]
- 输出
- 4
- 输入
- sentences=["please wait","continue to fight","continue to win"]
- 输出
- 3
最优解：一步一步想明白
- 3记牢这一句:单词数等于空格数加一。因为格式规范,数空格比切单词省事得多。下面就一句一句地扫过去,每句数出空格、加一,再和当前最大值比一比。
- 4开始扫 句1,也就是 i can do it。把这句拆成一排字符格,空格用一个小方块 ␣ 标出来。空格计数从 0 开始;哪怕一个空格都没有,一句话里至少也有一个单词,所以单词数先记成 1。紫色指针待会儿从最左边一格一格往右走。
- 5指针走到第 1 格,是字母 i,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
- 6指针走到第 2 格,这是一个空格,把它标绿。空格计数从 0 加到 1。空格是单词的分隔符,数到 1 个空格,就意味着眼下已经分出 2 段单词。
- 7指针走到第 3 格,是字母 c,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
- 8指针走到第 4 格,是字母 a,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
- 9指针走到第 5 格,是字母 n,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
- 10指针走到第 6 格,这是一个空格,把它标绿。空格计数从 1 加到 2。空格是单词的分隔符,数到 2 个空格,就意味着眼下已经分出 3 段单词。
- 11指针走到第 7 格,是字母 d,不是空格,空格计数不动,仍是 2。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 3。
- 12指针走到第 8 格,是字母 o,不是空格,空格计数不动,仍是 2。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 3。
- 13指针走到第 9 格,这是一个空格,把它标绿。空格计数从 2 加到 3。空格是单词的分隔符,数到 3 个空格,就意味着眼下已经分出 4 段单词。
- 14指针走到第 10 格,是字母 i,不是空格,空格计数不动,仍是 3。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 4。
- 15指针走到第 11 格,是字母 t,不是空格,空格计数不动,仍是 3。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 4。
- 16句1 扫完了,一共 3 个空格,单词数就是 3 加 1,等于 4。它比之前记的最大值 0 还大,把最大值刷新成 4。把这句的结果记进右边面板,接着看下一句。
- 17开始扫 句2,也就是 red fox。把这句拆成一排字符格,空格用一个小方块 ␣ 标出来。空格计数从 0 开始;哪怕一个空格都没有,一句话里至少也有一个单词,所以单词数先记成 1。紫色指针待会儿从最左边一格一格往右走。
- 18指针走到第 1 格,是字母 r,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
- 19指针走到第 2 格,是字母 e,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
- 20指针走到第 3 格,是字母 d,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
- 21指针走到第 4 格,这是一个空格,把它标绿。空格计数从 0 加到 1。空格是单词的分隔符,数到 1 个空格,就意味着眼下已经分出 2 段单词。
- 22指针走到第 5 格,是字母 f,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
- 23指针走到第 6 格,是字母 o,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
- 24指针走到第 7 格,是字母 x,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
- 25句2 扫完了,一共 1 个空格,单词数就是 1 加 1,等于 2。它没有超过当前最大值 4,最大值保持不变。把这句的结果记进右边面板,接着看下一句。
- 26开始扫 句3,也就是 go。把这句拆成一排字符格,空格用一个小方块 ␣ 标出来。空格计数从 0 开始;哪怕一个空格都没有,一句话里至少也有一个单词,所以单词数先记成 1。紫色指针待会儿从最左边一格一格往右走。
- 27指针走到第 1 格,是字母 g,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
- 28指针走到第 2 格,是字母 o,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
- 29句3 扫完了,一共 0 个空格,单词数就是 0 加 1,等于 1。它没有超过当前最大值 4,最大值保持不变。把这句的结果记进右边面板,三句全数完了。
- 30三句全部数完:i can do it 有 4 个单词,red fox 有 2 个单词,go 有 1 个单词。里面最多的是 i can do it 的 4 个单词,舞台上把它的空格全标绿给你看,3 个空格切出 4 段。所以整组句子里单个句子的最多单词数就是 4。
⚠️ 容易写错的地方
✗ 错：直接把空格数当答案返回
✓ 对：单词数 = 空格数 + 1,别忘了那个加一
k 个空格把句子切成 k+1 段单词,漏掉加一会把每句都少数一个单词,是典型的差一错误
✗ 错：真的去按空格切分单词再数长度
✓ 对：只数空格再加一就够
题目保证单词间正好一个空格、首尾无空格,数空格与切单词等价,还省掉一次切分的开销
✗ 错：把所有句子的单词数加起来
✓ 对：要的是最大值,不是总和
题目问的是单个句子里最多多少单词,得逐句比较取最大,求和会答非所问
✗ 错：以为数空格加一对任意字符串都成立
✓ 对：它靠题面保证:句子非空、单词间正好一个空格、首尾无空格
空句子没有单词、连续空格或首尾空格都会让空格数加一失真;本题有格式保证才敢这么简化,超出这个前提要改判从空格到字母的边界
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mostWordsFound(self, sentences: List[str]) -> int:
return 1 + max(s.count(' ') for s in sentences)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int mostWordsFound(vector<string>& sentences) {
int ans = 0;
for (auto& s : sentences) {
int cnt = 1 + count(s.begin(), s.end(), ' ');
ans = max(ans, cnt);
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int mostWordsFound(String[] sentences) {
int ans = 0;
for (String s : sentences) {
int cnt = 1;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == ' ') {
++cnt;
}
}
ans = Math.max(ans, cnt);
}
return ans;
}
}复杂度
时间
O(总字符数)
设所有句子的字符总长为 L。每个字符最多被看一次:数空格就是把字符扫一遍。句子个数与总字符数都被这一遍覆盖,整体随总字符数线性增长
空间
O(1)
只用了空格计数、当前单词数、最大值这几个变量,不随输入规模增长。没有额外开与输入等长的数组或哈希表
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 句子中的最多单词数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路是什么?+
利用格式规范这个前提:单词间正好一个空格、首尾无空格,那么单词数就是空格数加一。逐句数空格再加一得到每句单词数,一路记住最大值就是答案。不必真的把句子切成一个个单词。
如果句子里可能有连续空格或首尾空格,还能这么做吗?+
那样数空格加一就会高估单词数。这时要么按空格切分后去掉空段再计数,要么在扫描时只在从空格进入非空格的那一刻算一个新单词。本题题面保证了规范格式,所以数空格的简法成立。
复杂度是多少?+
时间是所有字符总长的线性,每个字符看一次数空格。空间是常数,只用空格计数和最大值几个变量,不额外开与输入等长的结构。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 句子中的最多单词数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。