【2022-10-03每日一题】1784. 检查二进制字符串字段[Easy]
2022-10-03
1分钟阅读时长
2022-10-03每日一题：1784. 检查二进制字符串字段
难度：Easy
标签：字符串
给你一个二进制字符串 s ，该字符串 不含前导零 。
如果 s 包含 零个或一个由连续的 '1' 组成的字段 ，返回 true 。否则，返回 false 。
如果 s 中 由连续若干个 '1' 组成的字段 数量不超过 1，返回 true 。否则，返回 false 。
示例 1：
输入：s = "1001"
输出：false
解释：由连续若干个 '1' 组成的字段数量为 2，返回 false
示例 2：
输入：s = "110" 输出：true
提示：
1 <= s.length <= 100s[i] 为'0'或'1's[0]为'1'
方法一：
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
思路与算法
题目给定一个长度为 n 的二进制字符串 s，并满足该字符串不含前导零。现在我们需要判断字符串中是否只包含零个或一个由连续 1 组成的字段。首先我们依次分析这两种情况：
- 字符串 s 中包含零个由连续 1 组成的字段，那么整个串的表示为 00⋯00。
- 字符串 s 中只包含一个由连续 1 组成的字段，因为已知字符串 s 不包含前导零，所以整个串的表示为 1⋯100⋯00。
那么可以看到两种情况中都不包含 01 串。且不包含的 01 串的一个二进制字符串也有且仅有上面两种情况。所以我们可以通过原字符串中是否有 01 串来判断字符串中是否只包含零个或一个由连续 1 组成的字段。如果有 01 串则说明该情况不满足，否则即满足该情况条件。
代码
golang
func checkOnesSegment(s string) bool {
// 0 后面不能有 1
return !strings.Contains(s, "01")
}
php
class Solution {
/**
* @param String $s
* @return Boolean
*/
function checkOnesSegment($s) {
return !str_contains($s, "01");
}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 为字符串 s 的长度。
- 空间复杂度：O(1)，仅适用常量空间。
方法二：模拟
func checkOnesSegment(s string) bool {
n, cnt, idx := len(s), 0, 0
for idx < n && cnt <= 1 {
for idx < n && s[idx] == '0' { idx++ }
if idx < n {
for idx < n && s[idx] == '1' { idx++ }
cnt++
}
}
return cnt <= 1
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。