Leetcode: No.717 1-bit and 2-bit

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 <= len(bits) <= 1000.
bits[i] is always 0 or 1.

翻译
大意就是，现在有两种字符（我以下称为A和B），A可以用一位比特0表示，B可以用两位比特10或者11来表示。现在给出一个用比特数组（称为bits）表示的两种符号组成的字符串，已知bits最后1位是0，要求返回字符串最后一个字符是不是必须是A。
附加条件：bits长度在1-1000闭区间内。bits元素只可能是0或者1。
举例1：输入bits = [1, 0, 0]，应返回True。拆分为10-0
举例2：输入bits = [1, 1, 1, 0]返回False，拆分为11-10

初始解法：

很朴素的思路，从左往右扫，那么可能有以下几种情况：

1. bits[i] = 1，如果不考虑其左边的数，那么它一定是B的第一位比特，bits[i+1]一定存在但是无关紧要；
2. bits[i] = 0，如果不考虑其左边的数，那么它一定是A。

所以说我们可以使用一个指针，遇到1右移2位，遇到0右移1位，直到最后，判断上一次是右移多少位就知道最后1个0是属于A还是B了。
代码：

# Time:  O(n)
# Space: O(1)
class Solution(object):
    def isOneBitCharacter1(self, bits):
        i = 0
        isTwoDigits = False
        while i < len(bits):
            if bits[i] == 1:
                i += 1
                isTwoDigits = True
            else:
                isTwoDigits = False
            i += 1
        return not isTwoDigits

进阶解法

经过仔细思考可以发现：一定要扫完整个数组吗？答案是未必。
由于已知条件是最后1位是0，其实可以从右向前扫。
可以有如下思考：

1. 假如最后的0前面是0，即...00，那么立刻可以返回True（只可能是...0-0）；
2. 假如是1，即...10，还未可知，得继续往前探（如110与10结果不同）；
3. 假如是...010，立刻得知应该返回False（只可能是...0-10）；
4. 假如是...110，仍然未知；
5. 考虑极端情况，若干连续1和最后1个0，那么1的个数的奇偶直接影响结果，也就是说必须扫完整个序列；
6. 综上考虑，从右向左，找到第二个0，那么就是0...0，中间是若干个（可能是0个）1，因为0不可能是2位bit字符的第一位，因此相当于从第二个0右边可以安全分离，只需要考虑其右边的数组，也就是⑤里面所说的情况，这样可以通过计算1的个数的奇偶来得到结果（举例来说，10110可以安全分为10-110，101110也可以安全分为10-1110，因为0不会和右边有瓜葛，保证右边仍然是有效完整的子字符串）；
7. 假如没有找到第二个0，那么也就是说本身就是⑤的情况，同样计算1的个数的奇偶来获得结果。

代码：

# Time:  O(n)
# Space: O(1)
class Solution(object):
    # 这里的解法就是用parity来记录1的奇偶，奇数个为1，偶数个为0
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        parity = 0
        for i in reversed(xrange(len(bits)-1)):
            if bits[i] == 0:
                break
            parity ^= bits[i]
        return parity == 0


if __name__ == "__main__":
    print(Solution().isOneBitCharacter([0]))
    print(Solution().isOneBitCharacter([1, 0, 0]))
    print(Solution().isOneBitCharacter([1, 1, 1, 0]))