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.

Difficulty: introductory

Starter code:

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

Solutions:
class Solution:
     def isOneBitCharacter(self, bits):
         """
         :type bits: List[int]
         :rtype: bool
         """
         
         """
         i = 0
         while i < len(bits)-1:
             if bits[i] == 1:
                 i += 2
                 
             else: # bits[i] is 0
                 i += 1
         # index: 0,1,2,..., L-2, L-1, where L denotes len(bits)
         if i == len(bits): # i comes from i+=2 case, bits[L-2] is 1, current i is one more of the last index, i.e. len(bits)
             return False   # ...10
         
         else:              # i comes from i+=1 case, bits[L-2] is 0, current i is the last index, len(bits)-1
             return True    # ...00
         """
         
         # Approach 2, much faster, scan from the back, till see a zero or exhaust the list
         # count how many one's there is.
         # Reason: ????...???0xxxx0  Only xxxx0 matters.  After a 0, start the process again.
         # 0 always marks the end of the earlier bits.
         count = 0
         i = len(bits)-2 # s[len(s)-1] the last item in s is always 0.
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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: # -1 for we have considered the last bit, another -1, we may use two bits at a time
                 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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         if len(bits)==1 and bits[0]==1: 
             return False
         n = len(bits)
         i = 0
         while(i < n):
             if i == n-1: return True
             else:
                 if bits[i] == 1:
                     i += 2
                 else: i+=1
         return False

class Solution:
     def isOneBitCharacter(self, bits):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         n = len(bits)
         i = 0
         current = 0
 
         while i < n:
             if bits[i] == 1:
                 current = 2
                 i += 2
             else:
                 current = 1
                 i += 1
 
         if current == 1:
             return True
         else:
             return False


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

class Solution:
     def isOneBitCharacter(self, bits):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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):
         """
         :type bits: List[int]
         :rtype: bool
         """
         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