I received another entry to my programming contest in email:


From: "Michael Scholz"

Sent: Thursday, April 01, 2004 5:34 PM


I started working on your programming contest, but I quickly tired of optimizing for how-clear-the-code-is. But then, when you posted some clear code with the slow algorithm, I figured I'd finish what I'd started; to at least provide an algorithmic alternative. Fixing up the performance by pre-allocating buffers, etc, would arguably be less clear. So I'll just submit a first draft (i.e. sans comments). And final draft, actually, I should go back to my regularly scheduled coding... :)


-Michael Scholz

THQ, Inc.


p.s. I'm kind of learn as I go on STL, so probably the blog-o-sphere would have much feedback about STL correctness. But at least I learned something new! (equal_range())


I’m including the source code at the end of the message.  Basically, this one is a 120-line C++ program.  Unlike the previous entries, it uses recursion rather than pure iteration.  I actually like this better.  What do you think?


This solution is close to mine, which I shall disclose fairly soon (I’m writing up the docs).  FYI, my program is in yet another language. :-)


#include <assert.h>

#include <fstream>

#include <map>

#include <set>


// why did I have to do this? Couldn't a simple std::string have compiled correctly?

class stlstring : public std::string



      stlstring() : std::string()


      stlstring(const std::string& arg) : std::string(arg)


      std::string& operator=(const std::string& _Right)


            return (this->std::string::operator=(_Right));


      bool operator<(const stlstring& _Right) const


            return (this->compare(_Right) < 0);



typedef std::multimap<stlstring,stlstring> tWordList;

typedef std::pair<stlstring,stlstring> tWordValue;

typedef std::set<stlstring> tStringSet;

char GetKeypadMapping(char characterToMap)


      if (characterToMap >= 'a' && characterToMap <= 'c')

            return '2';

      else if (characterToMap >= 'd' && characterToMap <= 'f')

            return '3';

      else if (characterToMap >= 'g' && characterToMap <= 'i')

            return '4';

      else if (characterToMap >= 'j' && characterToMap <= 'l')

            return '5';

      else if (characterToMap >= 'm' && characterToMap <= 'o')

            return '6';

      else if (characterToMap >= 'p' && characterToMap <= 's')

            return '7';

      else if (characterToMap >= 't' && characterToMap <= 'v')

            return '8';

      else if (characterToMap >= 'w' && characterToMap <= 'z')

            return '9';


      assert(0); // input wasn't valid, Although I'm putting a filter on the wordlist to guarantee it.

    return '0';



void InitWordList(tWordList& rWordList, const char* pszFileName)


      const int MAX_STRING_LENGTH =48;

      char tempbuffer[MAX_STRING_LENGTH];

      std::ifstream iffile( pszFileName );

      tWordValue tempval;

      if( iffile )


            while ( iffile.good() ) // EOF or failure stops the reading



                  if (*tempbuffer)


                        tempval.first = tempbuffer;

                        tempval.second = tempbuffer;

                for (unsigned int mapIndex = 0;mapIndex<tempval.second.length();mapIndex++)


                              tempval.first[mapIndex] = GetKeypadMapping(tolower(tempval.second[mapIndex]));






      else {

            // cout << "ERROR: Cannot open file 'pszFileName'." << endl;



void FindMatchesRecursive(tStringSet& destSet,const tWordList& rWordList, const stlstring& input,const stlstring& prefix)


      stlstring saveString = prefix;




      size_t inputStringLength = input.length();

      for (unsigned int i=0;inputStringLength && i<=(inputStringLength);i++)


            for (unsigned int j=0;j<=i;j++)


                  stlstring prefixString = prefix;


                  stlstring testString = input.substr(j,i);

                  stlstring remainderString = "";

                  if (j+i < inputStringLength)

                        remainderString = input.substr(j+i,inputStringLength-j-i);


                  std::pair<tWordList::const_iterator,tWordList::const_iterator> rangeMatch=rWordList.equal_range(testString);

                  for (tWordList::const_iterator it = rangeMatch.first;it!=rangeMatch.second;++it)


                        saveString = prefixString;








void main(void)


      tWordList wordlistMap;

      tStringSet answer;


      stlstring inputString = "6423946369";


      stlstring nullString = "";



      for(tStringSet::iterator it = answer.begin();it!=answer.end();it++)


            char buff[20];

            sprintf(buff, "%s\n", it->c_str());