题目描述

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

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

如果 s 中 由连续若干个 '1' 组成的字段 数量不超过 1，返回 true 。否则，返回 false 。

示例 1：

1
2
3
输入：s = "1001"
输出：false
解释：由连续若干个 '1' 组成的字段数量为 2，返回 false

示例 2：

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

提示：

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

来源：力扣（LeetCode）

题解

模拟

1
2
3
4
5
6
7
8
9
10
public boolean checkOnesSegment(String s) {
    // 因为不包含前导零, 则必定以 1 开头, 如果中间出现 0 以后, 再次遇到 1 则不满足要求
    int n = s.length();
    boolean check = false;
    for (int i = 0; i < n; i++) {
        if (check && s.charAt(i) == '1') return false;
        if (s.charAt(i) == '0') check = true;
    }
    return true;
}
  • 时间复杂度： O(n)
  • 空间复杂度： O(1)

submissions-2022100301

正则表达式

1
2
3
4
5
6
public boolean checkOnesSegment(String s) {
    String pattern = "0+1+";
    Pattern r = Pattern.compile(pattern);
    Matcher m = r.matcher(s);
    return !m.find();
}
  • 时间复杂度： O(n)
  • 空间复杂度： O(1)

submissions-2022100302

寻找 “01” 字符串

1
2
3
4
public boolean checkOnesSegment(String s) {
    // 因为不包含前导零, 不存在 "0" 开头的情况, 所以如果 "1" 不连续, 则必定存在 "01" 字符串
    return !s.contains("01");
}
  • 时间复杂度： O(n)
  • 空间复杂度： O(1)

submissions-2022100303

参考资料

__END__