[cpp] #include <string> #include <vector> #include <iostream> using namespace std; class BinaryCode{ public: vector<string> decode(string message){ //prepare the basic return value vector<string> result; result.push_back( "NONE" ); result.push_back( "NONE" ); if( message.empty() ) return result; /* set down the value that can be deducted form 0 or 3 */ string module; for( int i=0; i<message.length(); ++i) module.push_back( 'x' ); for( int i=0; i<message.length(); ++i ){ if( message[i] == '0' ){ module[i] = '0'; if( i-1 >= 0 ) module[i-1] = '0'; if( i+1 < message.length() ) module[i+1] = '0'; } else if( message[i] == '3' ){ module[i] = '1'; if( i-1 >= 0 ) module[i-1] = '1'; if( i+1 < message.length() ) module[i+1] = '1'; } } /* set down the value can be deducted from 1 or 2 */ for( int k=0; k<=1; ++k ){ if( module[0] != '1'- k ){ string tmp = module; /* process the [0] unit */ tmp[0] = '0'+ k; /* process the [1] unit */ char ch = message[0] - tmp[0] + '0'; /*事實上ch可能算出2來，如message="22111",tmp[0]='0'*/ if( ch!='0' && ch!='1' ){ goto nosolution; } if( (module[1] != 'x') && (ch!=module[1]) ){ goto nosolution; } else{ tmp[1] = ch; } /* process [2]..[length-1] units */ for( int i=2; i<tmp.length(); ++i ){ ch = message[i-1] - tmp[i-1] - tmp[i-2] + '0' + '0'; if( ch!='0' && ch!='1' ){ goto nosolution; } if( (module[i] != 'x') && (ch != module[i]) ){ goto nosolution; } else{ tmp[i] = ch; } } /*add it to the result*/ result[k] = tmp; nosolution: ; } } return result; }; private:
