some algorithmic puzzles, tutorials, interview questions... and stuff...

Monday, October 26, 2009

How to find all possible words from a phone number

The problem statement: Most phone numbers these days are like 1-800-COOLSTUFF, which means you have to type 1-800-266578833 on your phone to dial. Given an array of numbers like "266578833" above, find all the words which could be formed from them. The problem is obviously exponential in complexity. Assuming each phone key holds 3 letters and having the array "266578833", there are 3*3*3*3*3*3*3*3*3 possible combinations, which means 39. So any algorithm has to be at least O(3n), where n is the size of the array of numbers.

The problem is easily solved in a recursive way: take each number and see which letters are assigned to it. Take each letter in turn, and each turn generate all possible combinations with the other letters:


   1:  //keep here the vector of letters
   2:  //like on position 5, the letters "jkl", which are on key 5 of a phone
   3:  vector<string> words;
   4:   
   5:  void generateWords(int* vec, int size, int index, vector<char>* currentWord) {
   6:      if (index == size) {//print if we reached the end
   7:          for (int i = 0; i < size; i++)
   8:              cout << currentWord->at(i);
   9:          cout << endl;
  10:          return;
  11:      }
  12:      //otherwise take each letter from the current key and add it to the stack
  13:      //then generate combinations with the other keys
  14:      for (int i = 0; i < words[vec[index]].size(); i++) {
  15:          currentWord->push_back(words[vec[index]][i]);
  16:          generateWords(vec, size, index + 1, currentWord);
  17:          currentWord->pop_back();
  18:      }
  19:  }

To call this, "words" needs to be initialized, like this:

   1:      words.push_back("");    //0
   2:      words.push_back(".,'"); //1
   3:      words.push_back("abc"); //2
   4:      words.push_back("def"); //3
   5:      words.push_back("ghi"); //4
   6:      words.push_back("jkl"); //5
   7:      words.push_back("mno"); //6
   8:      words.push_back("pqrs");//7
   9:      words.push_back("tuv"); //8
  10:      words.push_back("wxyz");//9
  11:      int size = 3;
  12:      int vec[] = { 2, 5, 8 };
  13:      vector<char> currentWord;
  14:      generateWords(vec, size, 0, &currentWord);

2 comments:

  1. Where is the matching to determine if it is actually a "word"? Doesn't this just generate all possible combinations to which you would still need to do the comparison against a dictionary of sorts?

    ReplyDelete
  2. Right. I think "word" was not the best choice. In case only real existing words are needed, then the results would need to be compared to an existing dictionary.

    ReplyDelete