1784

1784. Check if Binary String Has at Most One Segment of Ones (Easy)

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'.

Related Topics:
Greedy

Solution 1.

When done is true, it means that we've already done visiting the first continuous segment of 1s.

If we continue to see 1 after done is already true, return false.

// OJ: https://leetcode.com/problems/check-if-binary-string-has-at-most-one-segment-of-ones/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool checkOnesSegment(string s) {
        int done = false;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '1') {
                if (done) return false;
            } else done = true;
        }
        return true;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/check-if-binary-string-has-at-most-one-segment-of-ones/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool checkOnesSegment(string s) {
        for (int i = 1; i < s.size(); ++i) {
            if (s[i - 1] == '0' && s[i] == '1') return false;
        }
        return true;
    }
};