{x}
blog image

1-bit and 2-bit Characters

We have two special characters:

  • The first character can be represented by one bit 0.
  • The second character can be represented by two bits (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 <= 1000
  • bits[i] is either 0 or 1.

Solution Explanation

This problem asks whether the last character in a binary array representing 1-bit and 2-bit characters is a 1-bit character. A 1-bit character is represented by 0, and a 2-bit character is represented by 10 or 11. The input array always ends with 0.

The solution uses a single-pass iterative approach to efficiently determine this.

Algorithm:

  1. Initialization: Initialize an index i to 0. This index will traverse the bits array. n stores the length of the array.

  2. Iteration: The while loop iterates through the array until the second to last element.

  3. Character Decoding:

    • If bits[i] is 0, it's a 1-bit character, so i increments by 1.
    • If bits[i] is 1, it's a 2-bit character, so i increments by 2 (to skip the next bit).

  4. Last Character Check: After the loop, if i is equal to n - 1, it means the last character is a 1-bit character because the loop stopped before reaching the last element. Otherwise, the last character is a part of a 2-bit character.

  5. Return Value: The function returns true if the last character is a 1-bit character; otherwise, it returns false.

Time Complexity: O(n), where n is the length of the bits array. The loop iterates through the array at most once.

Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Explanation (Python):

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i, n = 0, len(bits)
        while i < n - 1:
            i += bits[i] + 1
        return i == n - 1

The Python code directly implements the algorithm described above. i += bits[i] + 1 cleverly handles both 1-bit and 2-bit character decoding in a concise way.

Code Explanation (Java, C++, Go, JavaScript):

The Java, C++, Go, and Javascript codes are very similar to the Python code, demonstrating the algorithm's straightforward implementation across different languages. The core logic of iterating through the array and incrementing the index based on the bit values remains consistent. They all achieve the same O(n) time complexity and O(1) space complexity.