1-bit and 2-bit Characters

• LeetCode: 1-bit and 2-bit Characters

• Problem:

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

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. 

The given string will always end with a zero.

• Note:

1. 1 <= len(bits) <= 1000.

2. bits[i] is always 0 or 1.

• Examples:

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.

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.

• Analysis:

Defined two modes: one_bit mode and two_bits mode,

Loop the array and follow the rules,

    1. bits[i] == 0, index goes 1 step, one_bit mode

    2. bits[i] == 1, index goes 2 step, two_bits mode

Finally, the mode is tow_bits mode, return false. Otherwise, return true.

• Code - Java:

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int len = bits.length;
        int pos = 0;
        boolean one = true;
        for (int i = 0; i < len; i++) {
            one = true;
            if (bits[i] == 1) {
                i++;
                one = false;
            }
        }
        return one;
    }
}

• Code - C++:

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int len = bits.size();
        int pos = 0;
        bool one = true;
        for (int i = 0; i < len; i++) {
            one = true;
            if (bits[i] == 1) {
                i++;
                one = false;
            }
        }
        return one;
    }
};

• Code - Python:

class Solution(object):
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        bitsLen = len(bits)
        pos = 0
        one = True
        i = 0
        while i < bitsLen:
            one = True
            if bits[i] == 1:
                i += 1
                one = False
            i += 1
        return one

• Code - C:

bool isOneBitCharacter(int* bits, int bitsSize) {
    int pos = 0;
    bool one = 1;
    for (int i = 0; i < bitsSize; i++) {
        one = 1;
        if (bits[i] == 1) {
            i++;
            one = 0;
        }
    }
    return one;
}

• Time Complexity: O(N), N is the length of input array

• Space Complexity: O(1)