打印从数字创建的可能字符串

Question

给定一个 10 位数字的电话号码，我们必须打印由此创建的所有可能的字符串。数字的映射与手机键盘上的数字映射完全相同。

即对于 1,0->没有信 对于2-> A,B,C

例如，1230 平均日增重 BDG CDG AEG...

c/c++ 中解决这个问题的最佳解决方案是什么？

Answer 1

我认为递归解决方案适合这个问题。所以像这样：

def PossibleWords(numberInput, cumulative, results):
    if len(numberInput) == 0:
        results.append(cumulative)
    else:
        num = numberInput[0]
        rest = numberInput[1:]
        possibilities = mapping[num]
        if len(possibilities) == 0:
            PossibleWords(rest, cumulative, results)
        else:
            for p in possibilities:
                PossibleWords(rest, cumulative + p, results)

result = []
PossibleWords('1243543', '', result)

Answer 2

无需递归。这是一个迭代方法的示例。它打印出所有可能性，但您可能不完全喜欢它的行为。问题留给读者自己去发现;-)

string tab[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
string s="1201075384"; //input string

for(int mask=0;mask<1048576;mask++)//4^10, trying all the posibilities
{
  int m=mask;
  string cur="";
  for(int i=0;i<s.size();i++,m/=4)  
    if (m%4<tab[s[i]-'0'].size())
      cur+=tab[s[i]-'0'][m%4];
  cout<<cur<<endl;
}

Answer 3

Smashery 的 python 解决方案的 C++ 版本：

string getMapping(int num){
    assert(num>=2 && num<=9);

    switch(num){
        case 2:
            return "ABC";
        case 3:
            return "DEF";
        case 4:
            return "GHI";
        case 5:
            return "JKL";
        case 6:
            return "MNO";
        case 7:
            return "PRS";
        case 8:
            return "TUV";
        case 9:
            return "WXY";
        default:
            return " ";
    }
}


// Recursive function
void generateWords(string input, string cumulative, vector<string> &result){

    if(input.length() == 0){
        result.push_back(cumulative);
    }
    else{
        int num = input.at(0) - '0';
        string rest = input.substr(1, input.length()-1);
        string mapString = getMapping(num);
        if(mapString.compare(" ") != 0){
            for(int i=0; i<mapString.length(); i++){
                generateWords(rest, cumulative+mapString.at(i), result);
            }
        }
        else{
            assert(1==0);
        }
    }
}


void process(){

    generateWords("4734", "", words);

}