题目描述

给定一个二进制字符串 s，该字符串 不含前导零。

如果 s 最多包含 一个由连续的 '1' 组成的字段，返回 true。否则，返回 false。

样例

输入：s = "1001"
输出：false
解释：字符串中的 1 没有形成一个连续字段。

输入：s = "110"
输出：true

限制

• 1 <= s.length <= 100
• s[i] 为 '0' 或 '1'。
• s[0] 为 '1'。

算法

(枚举) $O(n)$

1. 注意到合法的答案都类似于 1111100000 这样的。
2. 从前往后找到第一个不是 1 的位置 l，从后往前找到第一个不是 0 的位置 r。
3. 如果 l == r + 1，则返回 true。

时间复杂度

• 遍历数组一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool checkOnesSegment(string s) {
        const int n = s.size();
        int l = 0, r = n - 1;
        while (l < n && s[l] == '1') l++;
        while (r >= 0 && s[r] == '0') r--;
        return l == r + 1;
    }
};