patterncppMinor

Substitution cipher algorithm performance boost

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codereview cpp c++stackoverflow optimization algorithm performance dynamic-programming

substitutionalgorithmperformanceboostcipher

Problem

This algorithm is meant to read a string of numbers on an input, a naive substitution cipher code (A = 1, B = 2, ..., Z = 26) and output the number of ways the code could be interpreted (e.g. 25114 could mean 'BEAN', ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ and ‘BEKD’, hence output is 6).

It is working properly, but not fast enough, though. Is there a way to improve its performance? I commented it heavily, so it is easy to read.

#include 
#include 

using namespace std;

//Those are global, because handled by both functions
int ways;       //number of ways the code could be interpreted
string s;       //input

//Takes account of all the tuples after the one on position "start" using
//recursion
void findNextPossible(size_t start) {
    if(start + 2 > s, s.at(0) != '0') {
        ways = 0;
        test = true;
        someDeletedInTheMiddle = false;
        pos = s.find('0');
        //In this while I look for zeros
        while(pos != string::npos) {
            //Code with 30,40,... is not valid -> output 0
            if(s.at(pos - 1) > '2') {
                test = false;
                break;
            }
            //If delete some in the middle, output smaller by 1
            if((pos >= 2 && pos  2) someDeletedInTheMiddle = true;
            //Don't cosider the tuple with zero in it anymore
            s.erase(pos-1, 2);
            //Any other zero?
            pos = s.find('0', pos);
        }
        if(test) {
            if(!someDeletedInTheMiddle) ways++;
            //Process the rest
            for(size_t i = 0; i < s.length(); i++) {
                findNextPossible(i);
            }
        }       
        cout << ways << endl;
    }
    return 0;
}

Solution

You should use memoization on findNextPossible(), otherwise your algorithm has exponential complexity.

Also: the optimization obtained by looking for '0's will be no more useful once you use memoization... so the resulting code should become much, much smaller.

This is a possible implementation:

#include 
#include 
#include 
#include 

using namespace std;

int ways(std::string s) {
  static map cache;
  map::const_iterator f = cache.find(s);
  if (f!=cache.end()) return f->second;
  //  cout26) return cache[s] = ways(s.substr(1)); // cannot merge first two digits.                                                                       
  return cache[s] = ways(s.substr(1)) + ways(s.substr(2)); // two possible interpretations                                                               
}

const char *tests[]={"1213","12","214","205",0};

int main() {
  for (int i = 0; tests[i]; ++i) {
    cout<<tests[i]<<": "<<ways(tests[i])<<endl;
  }
}

Code Snippets

#include <string>
#include <map>
#include <iostream>
#include <cassert>

using namespace std;

int ways(std::string s) {
  static map<string,int> cache;
  map<string,int>::const_iterator f = cache.find(s);
  if (f!=cache.end()) return f->second;
  //  cout<<"ways("<<s<<")"<<endl;                                                                                                            
  if (s.size()==0) return 1;
  if (s[0]=='0') return 0; // no way the first digit is 0                                                                                     
  if (!isdigit(s[0])) return 0;
  if (s.size()==1) return 1; // only one possibility for a single digit                                                                       
  // here we have at least 2 digits                                                                                                           
  if (!isdigit(s[1])) return 0;
  int n = 10*(s[0]-'0')+(s[1]-'0');
  if (n>26) return cache[s] = ways(s.substr(1)); // cannot merge first two digits.                                                                       
  return cache[s] = ways(s.substr(1)) + ways(s.substr(2)); // two possible interpretations                                                               
}

const char *tests[]={"1213","12","214","205",0};

int main() {
  for (int i = 0; tests[i]; ++i) {
    cout<<tests[i]<<": "<<ways(tests[i])<<endl;
  }
}

Context

StackExchange Code Review Q#59645, answer score: 4

Revisions (0)

No revisions yet.