https://leetcode.com/problems/1-bit-and-2-bit-characters/description/
题目读起来怪怪的,意思就是有三种decode方式(0,10,11)目的是判断一串bit 是否只能用0 结尾来decode。
思路是写一个帮助函数canDecode,目的是判断一串bit 能否被合法的decode,然后把问题拆分成两部分,1)bits除最后一位外能否被decode;2)bits 最后一位能否被decode。
class Solution { public: bool canDecode(vector<int>& bits, int begin, int end) { if (begin > end) return true; if (begin == end) { return bits[begin] == 0; } //search all decode space if (bits[begin] == 0) { return canDecode(bits, begin+1, end);//decode as single } else { return canDecode(bits, begin+2, end); } } bool isOneBitCharacter(vector<int>& bits) { if (bits.back() == 1) { //the last is 1 return false directly return false; } return canDecode(bits, 0, bits.size()-2); } };