1-bit and 2-bit Characters
Sometimes a recursive approach to a problem might seem like a bad idea "because of the stack overhead and potential explosion of permutations and overly complicated logic"... yada, yada, yada.
Sure, sometimes such arguments are right on the target, but sometimes (many times) computer science problems can mirror life problems quite accurately, where the answer to the problem can be a boring "it depends".
Take a look at this problem by LeetCode:
https://leetcode.com/problems/1-bit-and-2-bit-characters/description/
We have two special characters. The first character can be represented by one bit
The problem statement is practically giving you the recipe on how to solve it.
I make the argument here that in such a case a basic recursive solution will do the trick quite well. It can be stated in four simple lines (literally) and since this is an fast-forward-moving tail recursion, it will be executing very fast.
Definitely it can be done interactively but I think the recursive solution here really does a great job in following the rules stated in the problem description in a very mathematical manner.
Hope you enjoy! Marcelo
public class Solution
{
public bool IsOneBitCharacter(int[] bits)
{
return IsOneBitCharacterInternal(bits, 0);
}
private bool IsOneBitCharacterInternal(int[] bits, int index)
{
if (index >= bits.Length) return false;
if (index == bits.Length - 1) return bits[index] == 0;
if (bits[index] == 1) return IsOneBitCharacterInternal(bits, index + 2);
return IsOneBitCharacterInternal(bits, index + 1);
}
}
Sure, sometimes such arguments are right on the target, but sometimes (many times) computer science problems can mirror life problems quite accurately, where the answer to the problem can be a boring "it depends".
Take a look at this problem by LeetCode:
https://leetcode.com/problems/1-bit-and-2-bit-characters/description/
We have two special characters. The first character can be represented by one bit
0. The second character can be represented by two bits (10or11).
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.
The problem statement is practically giving you the recipe on how to solve it.
Definitely it can be done interactively but I think the recursive solution here really does a great job in following the rules stated in the problem description in a very mathematical manner.
Hope you enjoy! Marcelo
{
public bool IsOneBitCharacter(int[] bits)
{
return IsOneBitCharacterInternal(bits, 0);
}
private bool IsOneBitCharacterInternal(int[] bits, int index)
{
if (index >= bits.Length) return false;
if (index == bits.Length - 1) return bits[index] == 0;
if (bits[index] == 1) return IsOneBitCharacterInternal(bits, index + 2);
return IsOneBitCharacterInternal(bits, index + 1);
}
}
Comments
Very nice, Marcelo! Interestingly even though I also think that your recursive solution models the problem very well, the first thought that came to my mind when I saw this problem is Huffman encoding and since this problem is actually using it, I decided to approach it from the point of view of an Huffman encoding decoder - if current element is 1 than we know we can skip 2 bits, and if current element is zero, we can skip only a single element. The code is here:
Reply Deleteclass Solution {
public:
bool isOneBitCharacter(const vector& bits) {
int i = 0;
for (; i < bits.size() - 1; i += bits[i] + 1) {}
return i == bits.size() - 1;
}
};
Have a splendid rest of the weekend!
Cheers,
Taras
also, here is a slightly less ugly version:
Deleteclass Solution {
public:
bool isOneBitCharacter(const vector& bits) {
int i = 0;
while (i < bits.size() - 1) i += bits[i] + 1;
return i == bits.size() - 1;
}
};
https://ideone.com/Y9bhbb
Oh I love the bits[i]+1, encapsulates the core of the problem so well! Brilliant!!!
DeleteHa, I'm glad that you liked it - it was mostly just to remove an extra if statement, since they hurt performance, but as a side effect they also made the solution a bit shorter. In your implementation you could also replaced
Deleteif (bits[index] == 1) return IsOneBitCharacterInternal(bits, index + 2);
return IsOneBitCharacterInternal(bits, index + 1);
with
return IsOneBitCharacterInternal(bits, index + bits[index] + 1);
which in theory should make your solution even faster and more elegant :)
Post a Comment
[γγ¬γΌγ ]