434. 字符串中的单词数

🟢   🔖  字符串  🔗 力扣 LeetCode

题目

Given a string s, return the number of segments in the string.

A segment is defined to be a contiguous sequence of non-space characters.

Example 1:

Input: s = "Hello, my name is John"

Output: 5

Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

Example 2:

Input: s = "Hello"

Output: 1

Constraints:

• 0 <= s.length <= 300
• s consists of lowercase and uppercase English letters, digits, or one of the following characters "!@#$%^&*()_+-=',.:".
• The only space character in s is ' '.

题目大意

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: "Hello, my name is John"

输出: 5

解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。

解题思路

思路一：拆分数组

我们可以将字符串 s 以空格作为分隔符拆分成一个数组，然后过滤掉空字符串，最后计算数组的长度（单词数量）。

1. 使用 split(' ') 方法将字符串按空格拆分成多个子字符串。
2. 使用 filter() 过滤掉数组中的空字符串（''），因为空字符串不是有效单词。
3. 返回过滤后的数组长度。

复杂度分析

• 时间复杂度： O(n)，其中 n 是字符串的长度。split 和 filter 操作都会遍历整个字符串。
• 空间复杂度： O(n)，split 方法会生成一个新数组。

思路二：遍历字符串

考虑到时间复杂度和空间复杂度，有一种优化解法，通过直接遍历字符串并计算单词数量，避免使用 split() 方法和 filter() 方法，从而减少内存消耗。

通过遍历字符串，在遇到非空字符时开始计数，当遇到空格时，我们认为一个单词已经结束。这样可以直接计算单词数量，而不需要先把整个字符串拆分成数组。

1. 遍历字符串 s，用一个布尔值 inWord 来标记当前是否在一个单词中。
2. 当遇到非空格字符时，如果当前不在一个单词中，说明一个新单词开始了，单词计数加 1。
3. 当遇到空格时，设置 inWord 为 false，表示当前没有在一个单词中。
4. 最后返回单词的数量。

复杂度分析

• 时间复杂度： O(n)，只遍历一次字符串。
• 空间复杂度： O(1)，只用常数空间来存储计数器和标记。

代码

拆分数组

/**
 * @param {string} s
 * @return {number}
 */
var countSegments = function (s) {
	return s.split(' ').filter((i) => i !== '').length;
};

遍历字符串

/**
 * @param {string} s
 * @return {number}
 */
var countSegments = function (s) {
	let count = 0;
	let inWord = false;

	for (let i = 0; i < s.length; i++) {
		if (s[i] !== ' ') {
			if (!inWord) {
				count++;
				inWord = true;
			}
		} else {
			inWord = false;
		}
	}

	return count;
};