Sponsored
Sponsored
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.
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.
1public class Solution {
2 public bool IsOneBitCharacter(int[] bits) {
3 int i = 0;
4 while (i < bits.Length - 1) {
5 i += bits[i] == 1 ? 2 : 1;
6 }
7 return i == bits.Length - 1;
8 }
9}The C# solution is analogous to the other solutions, iterating through the array and checking the increments based on bit value.
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).
Time Complexity: O(n), in the worst-case scenario where most bits are '1'.
Space Complexity: O(1).
Python solution using reverse iteration to determine parity in the sequence of '1's appearing before the closing '0'.