LeetCode 1784：检查二进制字符串字段的多种解法与状态机思维

今天刷 LeetCode 的每日一题，碰上 1784. 检查二进制字符串字段。题面不长：给你一个二进制字符串 s，判断由 1 组成的连续子串（题目里叫“字段”）是不是至多只能有一个。我第一眼看到“字段”这两个字，脑子里先想起数据库表字段、JSON 字段，稍一细看才发现，这里的字段是英文 segment 的直译，意思就是“连续的一段”。说白了，这道题问的是一串只有 0 和 1 的字符串里，1 的“聚集地”是不是只有一处。题目本身难度不高，但非常适合算法入门者和准备面试的人练手，因为它能同时带出字符串遍历、状态机、正则、边界条件这些基本功。接下来我把自己的完整复盘过程写下来，从题目模型到五种解法、正确性证明，再到我实际提交时踩过的坑，一次讲清楚。

1. 题目到底在考什么：读懂“字段”这个模型

1.1 原题描述与两个示例

原题原文：给你一个二进制字符串 s，如果字符串中由 1 组成的最大连续子字符串（字段）不超过一个，返回 true；否则，返回 false。

这里面有个很容易看懵的表述：“最大连续子字符串”。官方说的是“由 1 组成的最大连续子字符串（字段）”，其实“最大”在这里不是指长度最大，而是指连续的、不能再向外扩展的完整块。更准确的说法应该是“连续段”或“连续区块”。一个字符串可以由若干个这样的 1 段组成，中间用 0 隔开。我们只要统计这样的 1 段有几个，超过一个就返回 false。

1.2 别被名字劝退：这里的“字段”不是数据库字段

很多刚刷题的朋友看到“字段”两个字会习惯性地往数据库方向想，我一开始也这样。实际上这个翻译来自英文的 segment，它在字符串题目里的含义就是“由相同字符组成的连续片段”。你可以把字符串想象成一排灯，字符 1 表示灯亮，0 表示灯灭。字段就是一个连续的亮灯区间。题目要求的是：整排灯里，亮着的连续区间最多只能有一个。

这个类比能帮助我们定位真正的判断目标：要找的不是“1 的个数”，而是“1 的连续块数”。“110”里面 1 的总数是 2，但 1 的连续块是 1 个；“101”里面 1 的总数也是 2，但连续块是 2 个。一个字符串有 2 个 1 不一定非法，有 2 块 1 才非法。我见过不少同学把这两者搞混，后面的常见问题部分我会专门再讲。

1.3 检查的本质：字符串是否符合 010* 模式

把问题再形式化一点：一个二进制字符串里，1 的连续段至多一个，意味着所有出现在字符串里的 1 必须一个接一个紧挨在一起，不能中间被 0 隔开。所以合法的字符串只有三种形态：

• 全是 0，比如 "000"，1 的段数是 0；
• 0 前缀后面跟着一段连续的 1，比如 "00111"；
• 0 前缀、中间一段连续的 1、后面再跟 0 后缀，比如 "0011100"。

把这三类合并成一条正则表达式就是0*1*0*。也就是说，这道题表面上是“检查二进制字符串字段”，实质上是问：这个字符串是不是 010* 这种形式。我从一开始就没急着写代码，而是先把这个模型想透，后面所有解法都是从这一个判断出发的。

2. 五种实现方案：从暴力扫描到状态机

2.1 解法一：线性扫描计数

最直观的解法是遍历字符串，数一数一共有几个 1 连续段。关键逻辑是：什么时候算一个新段？当当前位置是 '1'，并且它左边不是 '1'（也就是当前字符是段的开头）时，段数加一。第一段的开头还要考虑位置 0，所以要加一个“i == 0”的判断。

class Solution: def checkOnesSegment(self, s: str) -> bool: cnt = 0 n = len(s) for i in range(n): if s[i] == '1' and (i == 0 or s[i - 1] == '0'): cnt += 1 if cnt > 1: return False return True

时间复杂度 O(n)，空间复杂度 O(1)。这个写法最贴近问题定义，几乎不需要额外知识，是面试时最保险的解法。有一个容易被忽视的点：当整个字符串都是 0 时，cnt 始终是 0，0 小于等于 1，返回 true，这是符合题意还是不符合题意？要搞清楚：题目说的是“由 1 组成的字段至多一个”，0 个字段当然至多一个，所以返回 true。我见过有人在这里写了cnt == 0 or cnt == 1之类的冗余判断，其实没必要。

2.2 解法二：split 切分与长度判断

Python 选手可以用 split 一行把问题解决：用字符 '0' 把字符串切开，剩下的非空片段就是 1 连续段。然后数一下非空片段的数量是否不超过 1。

class Solution: def checkOnesSegment(self, s: str) -> bool: return len([part for part in s.split('0') if part]) <= 1

这个解法很 Pythonic，但它不像表面看起来那么“取巧”。“101”被切出来是两个片段 "1" 和 "1"，长度是 2，返回 false；“0110”被切出来是空串、"11"、空串，过滤空串后只有一个片段，返回 true。本质上它做了和线性扫描一样的事情，只是把“找连续段”的活交给了 split 的底层实现。要注意的是 split 会额外创建一个列表，在 n 很大的时候内存开销比计数法高，不过这道题 n 最大只有 100，完全不用担心。

2.3 解法三：正则全匹配

如果我们已经知道合法字符串属于 010*，那最直接的实现就是写一条正则，用 fullmatch 判断整个字符串完全匹配：

import re class Solution: def checkOnesSegment(self, s: str) -> bool: return re.fullmatch(r'0*1*0*', s) is not None

正则表达式0*1*0*表示：任意多个 0，然后任意多个 1，再然后任意多个 0。注意这里每一步都是“任意多个”，所以空字符串、全 0、全 1 都能匹配。这里最容易翻车的点是：必须使用 fullmatch（完全匹配），不能使用 search 或 match，后面踩坑部分我会专门展开。正则解法不是我平时会优先提交的答案，但在讲解思路时非常好用，因为它把题目模型直接翻译成了规则。Java 里对应的写法是s.matches("0*1*0*")，C++ 里可以用std::regex_match(s, std::regex("0*1*0*"))，思路完全一样。

2.4 解法四：双指针扫过整个串

双指针解法把“010*”拆成三个连续的阶段：先跳过前导 0，再跳过一段连续的 1，最后检查剩余的字符里还有没有 1。

class Solution: def checkOnesSegment(self, s: str) -> bool: n = len(s) i = 0 # 第一阶段：跳过前导 0 while i < n and s[i] == '0': i += 1 # 如果已经结束，说明全是 0 if i == n: return True # 第二阶段：跳过唯一的一个 1 连续段 while i < n and s[i] == '1': i += 1 # 第三阶段：剩下的必须是 0，一旦出现 1 就违规 while i < n: if s[i] == '1': return False i += 1 return True

这个写法的思路比计数法更接近“模型”：它不是在数段数，而是直接验证字符串的形状是不是 010*。如果在跳完那一段 1 之后还能碰到 1，说明 1 被 0 分成了两段；“1001”在这个逻辑下会在第三阶段遇到下标 3 的 '1'，直接返回 false。双指针写法的时间空间复杂度都是 O(n)/O(1)，而且不容易踩到负数索引的坑，我推荐没把握的同学优先用这种。

2.5 解法五：三状态自动机

从状态机的角度看，检查过程可以分成三个状态：

• 状态 0：还没有进入 1 字段（处于前导 0 区域）；
• 状态 1：正在 1 字段内部；
• 状态 2：已经离开 1 字段（处于后缀 0 区域）。

每读一个字符，根据当前状态做迁移。如果已经进入状态 2 却又碰到 '1'，说明 1 字段不止一个，直接返回 false。

class Solution: def checkOnesSegment(self, s: str) -> bool: state = 0 for ch in s: if ch == '1': if state == 2: return False state = 1 else: # ch == '0' if state == 1: state = 2 return True

状态机解法看起来比计数法复杂，但它把“合法模式”的形式化表达推向极致：状态 0 → 状态 1 → 状态 2 的路径清晰对应 010* 的识别过程。很多人觉得状态机是高大上的东西，其实它的核心就一句话：记住当前处于哪个阶段，根据新输入决定下一步怎么走。这个思维在解析 HTTP 头、JSON、CSV 等文本格式时非常常用，后面第五章我会再展开。

2.6 五种方案横向对比

真正面试时，我一般会先讲计数法，因为它的语义最贴近题目、几乎不会被追问；如果面试官问“还有没有更优雅的写法”，再补充正则或 split。这五种方案的差异其实都在表达层面，底层判断逻辑完全等价。

3. 正确性与边界：为什么这些解法都成立

3.1 从“字段数”到“010*”的等价性证明

不少读者可能觉得“代码 AC 了，证明无所谓”。但简单题正是练证明的好机会，这里我用几句话说明白为什么这些解法都对。

先证明“合法性 => 010*”：如果字符串里 1 的连续段至多一个，那么所有 1 一定集中在从左到右的某个连续区间 [l, r] 内。区间之前的字符不可能是 1，否则它要么和 [l, r] 连在一起（那区间就不是从 l 开始），要么自成一段（那字段就至少两个），都会矛盾；区间之后的字符同理也不可能是 1。因此字符串只能是若干个 0、再一段连续的 1、再若干个 0，即 010*。

再证明“010* => 合法性”：如果字符串满足 010*，中间那段 1 如果为空，1 的字段数是 0；如果不为空，因为 0 前缀和 0 后缀里都没有 1，整个字符串里就只有这一段 1，字段数恰好为 1。两边等价，所以检查“字段是否至多一个”和检查“字符串是否属于 010*”是一回事。

后面我在状态机、正则、双指针里的每一步，本质上都是对这个正则语言的识别，所以它们的结果必然一致。证明没有必要写得非常数学化，能自洽就行，但心里有这个等价关系，写任何解法都不会跑偏。

3.2 边界情况速查表

我每次提交前都会先跑一组手写的边界样例。针对这道题，我整理了一张表，覆盖了所有容易翻车的形态：

这张表几乎覆盖了所有边界：单字符、全 0、全 1、前导 0、后缀 0、字段被分隔、字段在中间。写完代码后顺手在脑内跑一遍这些样例，基本可以保证不翻车。如果是在编辑器里调试，直接把表格里的输入做成一个列表，循环打印结果就行。

3.3 复杂度、内存与语言特性细节

虽然 n 很小让这道题毫无性能压力，但养成关注复杂度习惯很重要。计数法、双指针、状态机都是严格 O(n) 时间、O(1) 额外空间，而且只扫描一遍字符串，这是最优复杂度。split 的时间是 O(n)，但因为要创建列表存储切分结果，额外空间是 O(n)；正则匹配在 Python 的 re 底层通常也是线性时间，但正则引擎匹配特殊模式时可能有一定常数开销。如果将来遇到长度达到百万级的大字符串，我建议优先用计数法或双指针，尽量避开 split 和正则。刷题时可以把这道题当作复杂度分析的练习：即便 n 很小，也明确说出每种做法的复杂度，这个习惯在面试里很加分。

4. 我实际提交时踩过的坑与排查记录

4.1 算错了对象：统计成 1 的总个数

这个坑是初学者最容易踩的。有人一看题目“由 1 组成的字段不超过一个”，就写成了s.count('1') <= 1。这个写法对 "110" 会返回 false，但正确答案是 true，因为 "110" 里有两个 1，可是它们连在一起，构成的是一个字段。如果按总数判断，等于把“字段数”和“1 的个数”混为一谈。这种错误不是单纯粗心，而是没有先建立“连续段”的模型。解决问题的方式就是先理解字段 = 连续块，再动手编码，而不是看到二进制字符串就直接统计字符数量。

4.2 被子串迷惑：“01” 存在不代表非法

还有一个很自然的想法：既然合法的模式是 010*，那只要没有 “01” 后面再接 1 的情况就行？于是有人写return "01" not in s or ...。这里有个陷阱：字符串 "0110" 是合法输入，它却包含子串 "01"（下标 0 到 1）。所以直接判断"01" in s会误判。正确检查“是否出现新的 1 字段”要看的是“离开 1 字段后再进入 1 字段”，也就是正则里的1+0+1模式，而不是简单看有没有 "01"。这也是为什么我在前面推荐先想清楚等价模型再写代码——被单个子串迷惑多半是因为没有模型。

4.3 Python 负数索引的隐性坑

Python 里s[-1]能取到最后一个字符，这个特性在写“当前字符的前一个字符”时特别容易埋雷。有人把计数法的判断写成：

if s[i] == '1' and s[i - 1] == '0' and i > 0:

这个顺序表面看着没问题，但 i 为 0 时s[-1]也能执行，取到的是字符串最后一个字符，不会报错。比如 s = "001"，i = 0 时执行s[-1] == '0'，发现最后一个字符是 '1'，条件为 false，于是漏掉了对首字符的判断，最终返回错误答案。在 Java 或 C++ 里这么写会直接越界崩溃，至少能暴露问题；Python 不崩，反而更难排查。我的经验是：涉及s[i-1]的判断，一定要把i == 0放在最前面，利用短路求值避免计算负数索引，或者干脆用双指针/状态机这类不依赖前一个字符的写法。

4.4 正则忘写 fullmatch，AC 变 WA

用正则时，如果写成re.search(r'0*1*0*', s)，结果会恒为真。原因是 search 会在字符串里寻找任意匹配的子串，而0*1*0*因为每一部分都能接受空串，会在任意位置以空字符串身份匹配成功。必须用re.fullmatch，或者用re.match加上$锚点：re.match(r'0*1*0*$', s)。这道题因为名字带“检查”，很多人第一反应就是正则匹配，结果 30 秒写完却怎么都 AC 不了。这个坑很隐蔽，我建议用正则解字符串匹配题时，心里默认第一选择是 fullmatch 或者明确带^、$锚点，除非题目真的要求子串匹配。

4.5 顺手收藏的一个取巧写法：strip('0')

最后分享一个我后来才发现的取巧写法，代码短到惊人：

class Solution: def checkOnesSegment(self, s: str) -> bool: return '0' not in s.strip('0')

思路是：先去掉字符串首尾的 0，如果剩下的部分还有 0，说明字符串中间还夹着 0，那 1 字段一定不止一个；如果剩下的部分没有 0，说明去掉首尾后只剩下连续的 1（或者全 0 串去掉后为空），合法。这个写法和我前面五种解法在逻辑上完全一致，只是把“前缀 0 和后缀 0”这个观察单独提了出来。我一般不会拿这种一行版本去面试，因为它解释起来反而需要多绕一步，但作为日常刷题的趣味解法，可以收藏。

5. 从一道简单题说开去：段模型与状态机的工程价值

5.1 连续段思想在同类题中的复现

“统计连续段”是算法题里一个高频思考模式，跟这道题强相关的题我能立刻想起一堆：485 题求最大连续 1 的个数，1446 题求连续相同字符的最大长度，1759 题统计同构子字符串数量，696 题要求数出所有形如 0/1 交替的二进制子串，443 题做字符串压缩时要按段处理。它们共同的核心都是：在遍历过程中识别“一个段的开始”和“一个段的结束”。比如 485 题，你同样要维护“当前是不是在 1 段里”这个状态，一遇到 0 就结算当前段的长度。练好 1784 这道题，等于给这整类题打了一个地基。我刷题时有个习惯：遇到一道简单但思路清晰的题，就主动想想它跟哪些题是同一个模型，然后放到一起复习，远比单道题重复十遍效果好。

5.2 状态机不只是面试题，也是解析器的底层

状态机解法在这道题里看起来有些“杀鸡用牛刀”，但它背后是一个非常重要的工程思想：任何文本解析都可以建模成“当前状态 + 当前输入 → 下一状态”。举个例子，解析 HTTP 响应头时，你可能要区分当前行是状态行、头部字段还是空行分隔符，写出的代码本质上就是状态机；写 JSON 的 tokenizer 时，你要区分当前处于字符串、数字还是对象结构的什么位置，同样要靠状态迁移。我在实际工作中写过一个简单的日志解析器，专门从每一行日志里提取等级和时间戳，最初的版本用大量 if 嵌套，后来重构成状态机，代码清晰度和可维护性都上了一个台阶。回到这道题，如果你能体会到“0 前缀 → 1 段 → 0 后缀”三个状态，以后再面对更复杂的格式识别，思路就会顺很多。

5.3 面试时怎么把这道题讲出层次

这道题如果出现在面试里，千万不要上来就甩一个一行 Python。我建议按这个顺序讲：先复述题意，澄清“字段”就是连续段；然后给出计数法，说明“遇到 1 且前一位不是 1 时计数加一”；接着主动补充一句“这个判断等价于检查字符串是否符合 010*”，再随手给出双指针或状态机的版本；最后把全 0、单字符、"101"、"1001" 这几个样例快速过一遍。这样不到两分钟就能展示出你会建模型、会证明、会做边界分析。面试官大概率会追问一句“还有更简单的实现吗”，这时再抛出 split 或正则，效果是最好的。拿我自己来说，这道题我前后用五种方法写过，隔了两个月再回头看，印象最深的反而不是 AC 本身，而是那个 010* 的模型。把简单题吃透，比赶着刷三遍难题更值得。