fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. int numDecodings(string s) {
  6.     int sol[50000];
  7.     if (s[0] == '0') {
  8.         return 0;
  9.     }
  10.     for (int i=0; i<=s.size(); i++) {
  11.         sol[i] = 0;
  12.     }
  13.     sol[0] = 1;
  14.     sol[1] = 1;
  15.     for (int i=2; i<=s.size(); i++) {
  16.         if (s[i-1] != '0') {
  17.             sol[i] = sol[i-1];
  18.         } 
  19.         if (s[i-2] != '0' && ((s[i-2]-'0')*10 + (s[i-1]-'0')) < 27) {
  20.                 sol[i]+=sol[i-2];
  21.         }
  22.     }
  23.     return sol[s.size()];
  24. }
  25.  
  26. int main() {
  27. 	printf("Solution: %d\n", numDecodings("110"));
  28. 	printf("Solution: %d\n", numDecodings("010"));
  29. 	printf("Solution: %d\n", numDecodings("1278"));
  30. 	return 0;
  31. }
Success #stdin #stdout 0.01s 5540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Solution: 1
Solution: 0
Solution: 2
https://ideone.com/RRWORT
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!