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.

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.



Note:
1 .
bits[i] is always 0 or 1.

Source: leetcode | Difficulty: EASY
Tags: Data structures

Starter code: class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        

Solutions:
class Solution:

	def isOneBitCharacter(self, bits):
		count = 0
		i = len(bits) - 2
		while i >= 0 and bits[i] is not 0:
			count += 1
			i -= 1
		if count % 2 == 0:
			return True
		else:
			return False


class Solution:

	def isOneBitCharacter(self, bits):
		if not bits:
			return False
		n = len(bits)
		index = 0
		while index < n:
			if index == n - 1:
				return True
			if bits[index] == 1:
				index += 2
			else:
				index += 1
		return False


class Solution:

	def isOneBitCharacter(self, bits):
		bits.insert(0, 0)
		for i in range(len(bits) - 2, -1, -1):
			if bits[i] == 0 or i == 0:
				return (len(bits) - i) % 2 == 0

	def isOneBitCharacter(self, bits):
		parity = bits.pop()
		while bits and bits.pop():
			parity ^= 1
		return parity == 0

	def isOneBitCharacter(self, bits):
		i = 0
		while i < len(bits) - 1:
			i += bits[i] + 1
		return i == len(bits) - 1


class Solution:

	def isOneBitCharacter(self, bits):
		i = 0
		n = len(bits)
		while i < n - 1:
			if bits[i] == 1:
				i += 2
			else:
				i += 1
		return i == n - 1


class Solution:

	def isOneBitCharacter(self, bits):
		l = len(bits)
		if l == 1:
			if bits[0] == 0:
				return True
			else:
				return False
		i = 0
		while 1:
			if bits[i] == 1:
				l -= 2
				i += 2
			else:
				l -= 1
				i += 1
			if l == 1:
				return True
			if l == 0:
				return False


class Solution:

	def isOneBitCharacter(self, bits):
		n = len(bits)
		if bits[n - 1] != 0:
			return False
		else:
			i = 0
			while i < n - 2:
				print((bits[i], ', '))
				if bits[i] == 1:
					if bits[i + 1] == 0 or bits[i + 1] == 1:
						i += 1
					else:
						return False
				elif bits[i] == 0:
					pass
				i += 1
			if bits[i] == 1:
				return False
			return True


class Solution:

	def isOneBitCharacter(self, bits):
		if len(bits) == 1 and bits[0] == 1:
			return False
		n = len(bits)
		i = 0
		while i < n:
			if i == n - 1:
				return True
			elif bits[i] == 1:
				i += 2
			else:
				i += 1
		return False


class Solution:

	def isOneBitCharacter(self, bits):
		i = 0
		while i < len(bits) - 1:
			if bits[i] == 0:
				i += 1
			elif bits[i] == 1:
				i += 2
		return i == len(bits) - 1


class Solution:

	def isOneBitCharacter(self, bits):
		i = len(bits)
		res = False
		while bits != []:
			e = bits.pop(0)
			if bits == [] and e == 0:
				return True
			if e == 1 and bits != []:
				bits.pop(0)
			i -= 1
		return res


class Solution:

	def isOneBitCharacter(self, bits):
		n = len(bits)
		flag = [0 for i in range(n)]
		i = 0
		while i < n - 1:
			print(i)
			if bits[i] == 1:
				flag[i + 1] = 1
			i = i + 1 + flag[i + 1]
		result = True if flag[-1] == 0 else False
		return result


class Solution:

	def isOneBitCharacter(self, bits):
		bits = ''.join(map(str, bits))
		return self.dfs(bits)

	def dfs(self, bits):
		if len(bits) == 0:
			return False
		elif len(bits) == 1:
			if bits[0] == '0':
				return True
		else:
			if bits[:2] == '10':
				if self.dfs(bits[2:]):
					return True
			elif bits[:2] == '11':
				if self.dfs(bits[2:]):
					return True
			elif bits[0] == '0':
				if self.dfs(bits[1:]):
					return True
			return False


class Solution:

	def isOneBitCharacter(self, bits):
		n = 0
		for i in range(-2, -len(bits) - 1, -1):
			if bits[i] == 1:
				n += 1
			else:
				break
		return n % 2 == 0


class Solution:

	def isOneBitCharacter(self, bits):
		bits.insert(0, 0)
		for i in range(len(bits) - 2, -1, -1):
			if bits[i] == 0 or i == 0:
				return (len(bits) - i) % 2 == 0