1784. Check if Binary String Has at Most One Segment of Ones
Description
Given a binary string s
βββββwithout leading zeros, return true
βββ if s
contains at most one contiguous segment of ones. Otherwise, return false
.
Example 1:
Input: s = "1001" Output: false Explanation: The ones do not form a contiguous segment.
Example 2:
Input: s = "110" Output: true
Constraints:
1 <= s.length <= 100
s[i]
ββββ is either'0'
or'1'
.s[0]
is'1'
.
Solutions
Solution 1: No '1' After '0'
Notice that the string $s$ does not contain leading zeros, which means $s$ starts with '1'.
If the string $s$ contains the substring "01", then $s$ must be a string like "1...01...", in which case $s$ has at least two consecutive '1' segments, which does not satisfy the problem condition, so we return false
.
If the string $s$ does not contain the substring "01", then $s$ can only be a string like "1..1000...", in which case $s$ has only one consecutive '1' segment, which satisfies the problem condition, so we return true
.
Therefore, we only need to judge whether the string $s$ contains the substring "01".
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 |
|
Solution 2
1 2 3 |
|