In this guide, you will get 717. 1-bit and 2-bit Characters LeetCode Solution with the best time and space complexity. The solution to -bit and -bit Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
The first character can be represented by one bit 0.
The second character can be represented by two bits (10 or 11).
Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.
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.
Constraints:
1 <= bits.length <= 1000
bits[i] is either 0 or 1.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
717. 1-bit and 2-bit Characters LeetCode Solution in C++
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
const int n = bits.size();
int i = 0;
while (i < n - 1)
if (bits[i] == 0)
i += 1;
else
i += 2;
return i == n - 1;
}
}; /* code provided by PROGIEZ */
717. 1-bit and 2-bit Characters LeetCode Solution in Java
class Solution {
public boolean isOneBitCharacter(int[] bits) {
final int n = bits.length;
int i = 0;
while (i < n - 1)
if (bits[i] == 0)
i += 1;
else
i += 2;
return i == n - 1;
}
} // code provided by PROGIEZ
717. 1-bit and 2-bit Characters LeetCode Solution in Python
class Solution:
def isOneBitCharacter(self, bits: list[int]) -> bool:
i = 0
while i < len(bits) - 1:
i += bits[i] + 1
return i == len(bits) - 1 # code by PROGIEZ
