0434. Number of Segments in a String

题目信息

题号:

0434

难度:

Easy

主题:

字符串、空格分隔、连续非空格片段、数量统计

原题:

LeetCode 0434

重点:

片段是最大连续非空格字符序列、多个空格不产生空片段、首尾空格不计数

题目重述

给定字符串 s,返回其中字符串片段的数量。一个片段定义为由一个或多个连续非空格字符组成的最大子串,片段之间由一个或多个普通空格字符分隔。

s.length 位于 [0, 300]。字符串可以为空,也可以在开头、结尾或片段之间包含多个空格。标点、数字和字母只要不是空格,都属于当前片段的一部分;连续空格之间不存在长度为零的片段。

自建示例

包含首尾和连续空格:

输入:s = "  red  blue42 "
输出:2
解释:两个最大连续非空格片段分别是 red 和 blue42,额外空格不产生片段。

只有空格:

输入:s = "   "
输出:0
解释:字符串中没有任何非空格字符,因此片段数量为 0。

只在空格后重新遇到非空格时计数

扫描字符串并维护是否正处于一个片段中。非空格字符在片段外出现时开启一个新片段并计数;片段内的后续字符不重复计数;普通空格把状态切回片段外。首尾空格和连续空格因此自然被忽略。

C++ 实现

class Solution {
public:
    int countSegments(std::string s) {
        int result = 0;
        bool inside = false;
        for (char c : s) {
            if (c == ' ') {
                inside = false;
            } else if (!inside) {
                ++result;
                inside = true;
            }
        }
        return result;
    }
};

代码分析

状态只记录当前字符是否属于已经计数的连续非空格段,标点和数字与普通非空格字符完全相同。时间复杂度为 O(n),额外空间为 O(1)。