package DP;

import java.util.*;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月17日 9:47
 * @description: 力扣 17电话号码的组合
 */
public class LetterCombination {
 public static void main(String[] args) {
 Scanner sr = new Scanner(System.in);
 String digits = sr.nextLine();
 List<String> ans = new ArrayList<>();
 ans = new LetterCombination_Solution().letterCombinations(digits);
 for(String x:ans){
 System.out.print(x+" ");
 }
 }
}


class LetterCombination_Solution{
 List<String> res = new ArrayList<>();
 public List<String> letterCombinations(String digits) {

 if(digits.length() == 0){
 return res;
 }
 Map<Character,String> str = new HashMap<>();
 str.put('2',"abc");
 str.put('3',"def");
 str.put('4',"ghi");
 str.put('5',"jkl");
 str.put('6',"mno");
 str.put('7',"pqrs");
 str.put('8',"tuv");
 str.put('9',"wxyz");
 int index = 0;
 StringBuffer trace = new StringBuffer();
 backtrace(res,trace,index,digits,str);
 return res;

 }

 public void backtrace(List<String> res,StringBuffer trace,int index,String digits,Map<Character,String> str){

 if(index == digits.length()){
 res.add(trace.toString());
 return;
 }

 String x = str.get(digits.charAt(index));
 for(int i = 0;i < x.length();i++){
 trace.append(x.charAt(i));
 backtrace(res,trace,index+1,digits,str);
 trace.deleteCharAt(index);
 }
 }

}