LeetCode 434. 字符串中的单词数

2022-02-23 HGNULB 约 6 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 434. 字符串中的单词数

题意分析

题目目标：给定一个字符串，统计其中「单词」的个数，这里单词的定义是极大的一段连续非空格字符。
核心约束：定义里只有空格是分隔符，其他任何字符——标点、数字、下划线——都算作单词的组成部分，这一点排除了按字母表判断的写法。题目允许字符串前后有空格、中间有连续多个空格、甚至整串都是空格，说明分隔符的数量和位置完全不受限，不能假设「空格数量等于单词数减一」。字符串长度上界不大，但只需要一个数字答案而不需要单词内容，这提示我们没必要真的把单词切出来。
边界处理：空串答案为 0；全是空格的串答案也为 0；首字符可能就是单词的开头，也可能是空格；末尾没有空格收尾时最后一个单词同样要被计入；连续多个空格之间不存在长度为 0 的「空单词」，不能重复计数。

解法：一次扫描计数

核心思路

最省事的写法是调用语言内置的分割函数，用空格切开再数一下非空片段。但这条路有两个问题：一是它在不同语言里行为不一致，Java 的 split(" ") 会在连续空格处产生空串、还会保留前导空串却丢掉尾部空串，必须额外过滤；二是它为了得到一个整数，先构造了一个包含所有单词副本的数组，白白付出 $O(n)$ 的额外内存和一次完整的字符串拷贝。更重要的是，面试里用分割函数等于把这道题的考点整个绕过去了，考官想看的恰恰是你如何手工处理边界。
换个角度想：答案是「单词的个数」，而每个单词恰好有一个首字符。既然单词与它的首字符一一对应，那么统计单词数就等价于统计有多少个位置是「某个单词的第一个字符」。而判断某个位置是不是单词首字符，只需要两个条件——它本身不是空格，并且它前面要么是空格要么根本没有字符。这样一来，根本不需要知道单词有多长、内容是什么，只需要在扫描时识别出这些起始位置。
因而边界判词可以直接写成：s[i] != ' ' && (i == 0 || s[i - 1] == ' ')。前半句确认当前位置属于单词，后半句确认它位于串首或紧跟分隔符。短路求值保证 i == 0 时不会访问 i - 1。

不变量是：扫描完前 i 个字符后，answer 等于前缀 s[0..i-1] 中满足上述判词的位置数，也就等于这个前缀已经开始的单词数。每个单词恰有一个首字符，每个满足判词的位置也必然开启一个单词，所以最终计数不漏不重。

解题步骤

初始化 answer = 0，从左到右扫描每个下标 i。

当前字符必须非空格；空格只负责分隔，连续多少个都不会直接增加答案。

当前字符非空格时，再判断 i == 0 || s[i - 1] == ' '。串首没有前驱，等价于前面存在一个虚拟空格；其他位置则要求前驱是真实空格。

两个条件同时成立就令 answer++。计数发生在单词开头，因此字符串末尾不需要收尾分支。

例如 s = " Hello, my name is John "，只有下标 2 的 H、m、n、i、J 满足判词，答案为 5。逗号不是空格，所以仍属于 Hello,；前导、连续和尾随空格都不会产生空单词。

代码实现

class Solution {
    public int countSegments(String s) {
        int answer = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ' ' && (i == 0 || s.charAt(i - 1) == ' ')) {
                answer++;
            }
        }
        return answer;
    }
}

func countSegments(s string) int {
	answer := 0
	for i := range s {
		if s[i] != ' ' && (i == 0 || s[i-1] == ' ') {
			answer++
		}
	}
	return answer
}

复杂度分析

时间复杂度：$O(n)$，n 为字符串长度。凭什么：单层循环遍历每个字符恰好一次，循环体内只有一次字符比较和至多两次赋值，全是常数操作。

空间复杂度：$O(1)$。只使用答案和循环下标，没有分割数组或字符串副本。

关键点总结

统计「段」的数量时，把计数锚定在段的起始位置而不是结束位置，能省掉循环之后的收尾处理。判定起始只需要看已经扫过的前驱，判定结束却要预读后继并额外考虑末尾截断，前者的边界永远更少。

边界判词是「当前非空格，且位于串首或前一位为空格」。两个条件缺一不可；括号顺序也要配合短路求值保护 i - 1。

把串首等价为「前面有一个虚拟空格」，能把首个单词与中间单词统一到同一判词中。

遇到分割类问题，优先考虑不物化中间结果。只要答案是个统计量而不是内容本身，就没必要为它分配 $O(n)$ 的数组，这在数据量大或内存受限时是实打实的差距。

面试视角：直接分割不仅分配中间数组，还容易把「只有普通空格才是分隔符」偷换成通用空白字符。先说出单词起点判词，再解释短路如何保护串首，代码和边界都能一次讲清。

易错点总结

错误写法：直接返回 s.split(" ").length。用例 s = "a b" → 连续空格切出一个空串，返回 3，正确答案是 2。

错误写法：改用 s.trim().split(" ").length 却仍不处理连续空格。用例 s = "a b" → 仍然返回 3；且用例 s = "" 时 trim 后 split 返回长度为 1 的数组，答案错成 1 而不是 0。

错误写法：统计空格数量再加一。用例 s = " Hello" → 两个空格算成三个单词，正确答案是 1。

错误写法：只判断当前字符非空格就计数。用例 s = "Hello" → 每个字符都被计入，返回 5，正确答案是 1。

错误写法：在空格处计数，即遇到空格且 inWord 为 true 时 answer++。用例 s = "Hello World" → 只有中间那个空格触发计数，末尾的 World 没有空格收尾，返回 1，正确答案是 2。

错误写法：判断前驱时忘记 i == 0。用例 s = "Hello" → 首轮访问 s[-1]，直接越界。

错误写法：用 Character.isLetter 判断单词字符。用例 s = "one,two" → 逗号被误当成分隔符，返回 2；按题意只有空格分段，正确答案是 1。

错误写法：判断分隔符时把制表符、换行等也算进去，写成 Character.isWhitespace。用例 s = "a\tb" → 按本题定义制表符属于非空格字符，整串是一个单词应返回 1，却被切成两个返回 2。

错误写法：认为空串需要特殊返回值而提前 return -1 或抛异常。用例 s = "" → 返回 -1，正确答案是 0，循环本身对空串天然返回 0，无需特判。

相似题目

题目	难度	考察点
58. 最后一个单词的长度	简单	只关心最后一段，从右往左先跳尾部空格再计长，考察反向扫描的边界
151. 反转字符串中的单词	中等	不仅要识别单词还要重排并规范化空格，需要物化内容而非仅计数
186. 反转字符串中的单词 II	中等	要求原地完成，用整体反转加逐词反转的两次翻转技巧把空间压到常数
557. 反转字符串中的单词 III	简单	保持单词顺序只反转内部字符，练习用双指针定位每段的起止下标
917. 仅仅反转字母	简单	分隔符与内容的角色互换，非字母字符固定不动，考察双指针跳过策略