We have two special characters:
0.10 or 11).Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.
Example 1:
Input: bits = [1,0,0] Output: true Explanation: The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.
Example 2:
Input: bits = [1,1,1,0] Output: false Explanation: The only way to decode it is two-bit character and two-bit character. So the last character is not one-bit character.
Constraints:
1 <= bits.length <= 1000bits[i] is either 0 or 1.This approach involves traversing the bit array to simulate decoding according to the rules. If a '0' is encountered, it signifies a one-bit character so you move one step forward. If a '1' is encountered, it indicates the start of a two-bit character ('10' or '11'), so you move two steps forward. The ultimate goal is to check whether the last character is reached after processing all bits, and it must land on a one-bit character.
The solution uses a simple loop to traverse through the array. When the loop reaches the second-to-last index, it checks if the last index can be reached with a one-bit character.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the bits array.
Space Complexity: O(1), as we are not using any extra space.
This approach involves reverse traversal, where we start checking bits from the end to see if the trailing '0' can be interpreted as a single one-bit character. Specifically, we count the number of continuous '1's preceding the last '0'. Based on whether this count is even or odd, we determine if the last character is a one-bit character (odd -> last is a part of an incomplete two-bit sequence, thus false; even -> last is a single-bit, thus true).
This C implementation calculates the number of continuous '1's from the second last element backwards and determines whether it is even or odd to decide if the last bit is a one-bit character.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), in the worst-case scenario where most bits are '1'.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Traversal and Check | Time Complexity: O(n), where n is the length of the bits array. |
| Approach 2: Reverse Traversal | Time Complexity: O(n), in the worst-case scenario where most bits are '1'. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,140 views views
Watch 9 more video solutions →Practice 1-bit and 2-bit Characters with our built-in code editor and test cases.
Practice on FleetCode