Распечатать возможные строки, созданные из числа

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

C ++ версия решения Smashery's python:

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