c++ - Number から作成された可能な文字列を出力する

Question

10 桁の電話番号が与えられた場合、そこから作成される可能性のあるすべての文字列を出力する必要があります。数字のマッピングは、電話のキーパッドとまったく同じです。

つまり、1,0 の場合 -> 2 の場合は文字なし -> A、B、C

たとえば、1230 ADG 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

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);

}

Answer 3

再帰的になる必要はありません。これは、開始するための反復アプローチの例です。すべての可能性が表示されますが、その動作が完全に気に入らない場合があります。キャッチは読者が発見するために残されています;-)

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;
}