# 717. 1-bit and 2-bit Characters

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

``````class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
int n = bits.size(), i = 0;
while (i < n - 1) {
if (bits[i] == 0) ++i;
else i+= 2;
}
return i == n - 1;
}
};
``````

``````class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
int n = bits.size(), i = 0;
while (i < n - 1) {
i += bits[i] + 1;
}
return i == n - 1;
}
};
``````

``````class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
if (bits.empty()) return false;
if (bits.size() == 1) return bits[0] == 0;
vector<int> t;
if (bits[0] == 0) {
t = vector<int>(bits.begin() + 1, bits.end());
} else if (bits[0] == 1) {
t = vector<int>(bits.begin() + 2, bits.end());
}
return isOneBitCharacter(t);
}
};
``````

``````class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
return helper(bits, 0);
}
bool helper(vector<int>& bits, int idx) {
int n = bits.size();
if (idx == n) return false;
if (idx == n - 1) return bits[idx] == 0;
if (bits[idx] == 0) return helper(bits, idx + 1);
return helper(bits, idx + 2);
}
};
``````

Gray Code

https://discuss.leetcode.com/topic/108743/java-solution-1-or-2

https://discuss.leetcode.com/topic/108766/c-both-iterative-and-recursive-solutions

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation