Leetcode 717 Solution

This article provides solution to leetcode question 717 (1-bit-and-2-bit-characters)
Categories:
Tags:
Access this page by simply typing in "lcs 717" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/1-bit-and-2-bit-characters

Solution

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        if (bits.size() == 1)
            return true;
        else if (bits.size() == 2)
            return bits[0] != 1;
        else if (bits[bits.size() - 2] == 0)
            return true;



        bool dp[bits.size()] = {false};



        for (int i = 0; i < bits.size() - 2; i++)
        {
            if (i == 0)
                dp[0] = bits[0] == 0;
            else if (i == 1)
                dp[1] = !(bits[0] == 0 && bits[1] == 1);
            else
            {
                if (bits[i] == 1)
                    dp[i] = dp[i - 2] && bits[i - 1] == 1;
                else if (bits[i - 1] == 1)
                    dp[i] = dp[i - 1] || dp[i - 2];
                else if (bits[i - 1] == 0)
                    dp[i] = dp[i - 1];
            }
        }



        return dp[bits.size() - 3] == false;
    }
};