Friday, November 21, 2014

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

1. Backtracking:
My first answer was wrong and I started to realize I hadn't quite understood the essence of backtracking.

http://stackoverflow.com/questions/27069642/passing-parameter-recursion-c-letter-combinations-of-a-phone-number

class Solution {
public:
    const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
       
    vector<string> letterCombinations(string digits) {
      
        vector<string> res;
        string combo;
        bt( res, combo,digits);
        return res;
    }
   
  void bt(vector<string> &res, string combo, string digits)
  {
      int i=combo.size();
      int len =digits.size();
   if ( i == len)
   {
    res.push_back(combo);
   
    return;
   }
   int idx = digits[i] - '0';
   string tmp = keyboard[idx];
   int s = tmp.size();
   for (int j = 0; j<s; j++)
   {
    bt(res, combo + tmp[j], digits);
   }
  }
};

2. Iterative
 class Solution {
public:
    const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
       
    vector<string> letterCombinations(string digits) {
      
        vector<string> res(1, "");
        string combo;
       
        int n=digits.size();
        vector<string> tmp;
        for(int i=0; i<n; i++)
        {
            int m = keyboard[digits[i]-'0'].size();
            int rsize =res.size();
            for (int k=0; k<rsize; k++)
            {
                string ts = res[k];
                for (int j=0; j<m; j++)
                   {
                    res[k] = res[k] + keyboard[digits[i]-'0'][j];
                    tmp.push_back(res[k]);
                    res[k] = ts;
                   }
            }
            res = tmp;
            tmp.clear();
        }
        return res;
    }
};

No comments:

Post a Comment