题目描述
思路解析动画文字版
记牢这一句:单词数等于空格数加一。因为格式规范,数空格比切单词省事得多。下面就一句一句地扫过去,每句数出空格、加一,再和当前最大值比一比。
开扫 句1 · i can do it：开始扫 句1,也就是 i can do it。把这句拆成一排字符格,空格用一个小方块 ␣ 标出来。空格计数从 0 开始;哪怕一个空格都没有,一句话里至少也有一个单词,所以单词数先记成 1。紫色指针待会儿从最左边一格一格往右走。
扫到字母 i · 句1 第 1 格：指针走到第 1 格,是字母 i,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
扫到空格 · 句1 第 2 格：指针走到第 2 格,这是一个空格,把它标绿。空格计数从 0 加到 1。空格是单词的分隔符,数到 1 个空格,就意味着眼下已经分出 2 段单词。
扫到字母 c · 句1 第 3 格：指针走到第 3 格,是字母 c,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
扫到字母 a · 句1 第 4 格：指针走到第 4 格,是字母 a,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
扫到字母 n · 句1 第 5 格：指针走到第 5 格,是字母 n,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
扫到空格 · 句1 第 6 格：指针走到第 6 格,这是一个空格,把它标绿。空格计数从 1 加到 2。空格是单词的分隔符,数到 2 个空格,就意味着眼下已经分出 3 段单词。
扫到字母 d · 句1 第 7 格：指针走到第 7 格,是字母 d,不是空格,空格计数不动,仍是 2。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 3。
扫到字母 o · 句1 第 8 格：指针走到第 8 格,是字母 o,不是空格,空格计数不动,仍是 2。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 3。
扫到空格 · 句1 第 9 格：指针走到第 9 格,这是一个空格,把它标绿。空格计数从 2 加到 3。空格是单词的分隔符,数到 3 个空格,就意味着眼下已经分出 4 段单词。
扫到字母 i · 句1 第 10 格：指针走到第 10 格,是字母 i,不是空格,空格计数不动,仍是 3。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 4。
扫到字母 t · 句1 第 11 格：指针走到第 11 格,是字母 t,不是空格,空格计数不动,仍是 3。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 4。
句1 结算 · 单词 4：句1 扫完了,一共 3 个空格,单词数就是 3 加 1,等于 4。它比之前记的最大值 0 还大,把最大值刷新成 4。把这句的结果记进右边面板,接着看下一句。
开扫 句2 · red fox：开始扫 句2,也就是 red fox。把这句拆成一排字符格,空格用一个小方块 ␣ 标出来。空格计数从 0 开始;哪怕一个空格都没有,一句话里至少也有一个单词,所以单词数先记成 1。紫色指针待会儿从最左边一格一格往右走。
扫到字母 r · 句2 第 1 格：指针走到第 1 格,是字母 r,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
扫到字母 e · 句2 第 2 格：指针走到第 2 格,是字母 e,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
扫到字母 d · 句2 第 3 格：指针走到第 3 格,是字母 d,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
扫到空格 · 句2 第 4 格：指针走到第 4 格,这是一个空格,把它标绿。空格计数从 0 加到 1。空格是单词的分隔符,数到 1 个空格,就意味着眼下已经分出 2 段单词。
扫到字母 f · 句2 第 5 格：指针走到第 5 格,是字母 f,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
扫到字母 o · 句2 第 6 格：指针走到第 6 格,是字母 o,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
扫到字母 x · 句2 第 7 格：指针走到第 7 格,是字母 x,不是空格,空格计数不动,仍是 1。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 2。
句2 结算 · 单词 2：句2 扫完了,一共 1 个空格,单词数就是 1 加 1,等于 2。它没有超过当前最大值 4,最大值保持不变。把这句的结果记进右边面板,接着看下一句。
开扫 句3 · go：开始扫 句3,也就是 go。把这句拆成一排字符格,空格用一个小方块 ␣ 标出来。空格计数从 0 开始;哪怕一个空格都没有,一句话里至少也有一个单词,所以单词数先记成 1。紫色指针待会儿从最左边一格一格往右走。
扫到字母 g · 句3 第 1 格：指针走到第 1 格,是字母 g,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
扫到字母 o · 句3 第 2 格：指针走到第 2 格,是字母 o,不是空格,空格计数不动,仍是 0。字母在单词内部,只有空格才是切分点,所以看到字母只管往右走。当前单词数按空格数加一算,是 1。
句3 结算 · 单词 1：句3 扫完了,一共 0 个空格,单词数就是 0 加 1,等于 1。它没有超过当前最大值 4,最大值保持不变。把这句的结果记进右边面板,三句全数完了。
回放 · 最多单词数 = 4：三句全部数完:i can do it 有 4 个单词,red fox 有 2 个单词,go 有 1 个单词。里面最多的是 i can do it 的 4 个单词,舞台上把它的空格全标绿给你看,3 个空格切出 4 段。所以整组句子里单个句子的最多单词数就是 4。
边界想清:单个词记 1、含一个空格记 2、最大值可能出现在任意一句,得逐句比过去。
面试重点:规范格式下单词数等于空格数加一、非规范时改判从空格到字母的边界、时间线性空间常数。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def mostWordsFound(self, sentences: List[str]) -> int: return 1 + max(s.count(' ') for s in sentences)复杂度
- 时间：O(总字符数)，设所有句子的字符总长为 L。每个字符最多被看一次:数空格就是把字符扫一遍。句子个数与总字符数都被这一遍覆盖,整体随总字符数线性增长
- 空间：O(1)，只用了空格计数、当前单词数、最大值这几个变量,不随输入规模增长。没有额外开与输入等长的数组或哈希表
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问如果句子里可能有连续空格或首尾空格,还能这么做吗?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一个排列
LeetCode 31 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题