434. 字符串中的单词数
434. 字符串中的单词数
题目
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
以空格作为分隔符拆分成一个数组,然后过滤掉空字符串,最后计算数组的长度(单词数量)。
- 使用
split(' ')
方法将字符串按空格拆分成多个子字符串。 - 使用
filter()
过滤掉数组中的空字符串(''
),因为空字符串不是有效单词。 - 返回过滤后的数组长度。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是字符串的长度。split
和filter
操作都会遍历整个字符串。 - 空间复杂度:
O(n)
,split
方法会生成一个新数组。
思路二:遍历字符串
考虑到时间复杂度和空间复杂度,有一种优化解法,通过直接遍历字符串并计算单词数量,避免使用 split()
方法和 filter()
方法,从而减少内存消耗。
通过遍历字符串,在遇到非空字符时开始计数,当遇到空格时,我们认为一个单词已经结束。这样可以直接计算单词数量,而不需要先把整个字符串拆分成数组。
- 遍历字符串
s
,用一个布尔值inWord
来标记当前是否在一个单词中。 - 当遇到非空格字符时,如果当前不在一个单词中,说明一个新单词开始了,单词计数加 1。
- 当遇到空格时,设置
inWord
为false
,表示当前没有在一个单词中。 - 最后返回单词的数量。
复杂度分析
- 时间复杂度:
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;
};