1784. 检查二进制字符串字段

🟢   🔖  字符串  🔗 力扣 LeetCode

题目

Given a binary string s ​​​​​without leading zeros , return true​​​ ifs containsat 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'.

题目大意

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

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

示例 1：

输入： s = "1001"

输出： false

解释： 由连续若干个 '1' 组成的字段数量为 2，返回 false

示例 2：

输入： s = "110"

输出： true

提示：

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

解题思路

由于字符串 不含前导零，说明字符串一定是由 '1' 开头，因此符合要求的字符串：

• 要么全是 '1'，如 '111111'；
• 要么 '1' 之后全是 '0'，如 '111000'；

因此，我们只需要从后往前遍历字符串，看是否有 '0' 之后又出现 '1' 的情况。

1. 从字符串的最后一位开始遍历字符串，判断段内是否有 '0'：

   • 遇到第一个 '1' 后，标记 hasOne 为 true。
   • 如果在已经标记了 hasOne 的情况下，继续遇到 '0'，说明至少存在两个连续的 '1' 段，所以返回 false。

2. 如果遍历完字符串没有发现多个 '1' 段的分隔符，则返回 true。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，只遍历字符串一次。
• 空间复杂度：O(1)，仅使用了常量空间来存储变量。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var checkOnesSegment = function (s) {
	let hasOne = false;
	for (let i = s.length - 1; i >= 0; i--) {
		if (s[i] == '1') {
			hasOne = true;
		}
		if (hasOne && s[i] == '0') {
			return false;
		}
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
1869	哪种连续子字符串更长	[✓]	字符串	🟢	🀄️ 🔗