# Poj Solution 1732

```http://poj.org/problem?id=1732

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class word{
String str,num;
public void change(){

}
}
public class Main {
static final int N = 100+10,M = 50000+10;
static Map mymap = new HashMap();
static int DP[] = new int[N],pre[] = new int[N],n,m;
static String str[] = new String[M],num,temp,Ans[] = new String[N];

public static void main(String[]args)throws Exception{
int i;
Scanner cin = new Scanner(System.in);
//Scanner cin = new Scanner(new FileInputStream("input.txt"));

while(cin.hasNext()){
num = cin.next();
n = cin.nextInt();
m = num.length();
mymap.clear();
for(i=0;i< n;++i){
str[i] = cin.next();
temp = change(str[i]);
mymap.put(temp, i);
}
solve();
}
}
static void solve(){
int i,j,k;
String tmp;
for(i=0;i<=m;++i){
DP[i] = -1;
pre[i] = -1;
}
DP[0] = 0;
for(i=1;i<=m;++i){
for(j=0;j< i;++j){
tmp = num.substring(j, i);
if(mymap.containsKey(tmp)){
k = (Integer)mymap.get(tmp);
if(DP[j]>-1 && (DP[i]==-1 || DP[i]>DP[j]+1)){
DP[i] = DP[j]+1;
pre[i] = k;
}
}
}
}
if(DP[m]==-1) System.out.println("No solution.");
else{
k = 0; j = m;
while(j>0){
Ans[k++] = str[pre[j]];
j -=str[pre[j]].length();
}
for(i=k-1;i>=0;--i){
if(i!=k-1) System.out.print(" ");
System.out.print(Ans[i]);
}
}
}
static String change(String world){
String ans="";
int i,len = world.length();
for(i=0;i< len;++i){
ans+=change(world.charAt(i));
}
return ans;
}
static char change(char c){
if(c=='i' || c=='j') return '1';
if(c>='a' && c<='c') return '2';
if(c>='d' && c<='f') return '3';
if(c>='g' && c<='h') return '4';
if(c=='k' || c=='l') return '5';
if(c=='m' || c=='n') return '6';
if(c=='p' || c=='r' || c=='s') return '7';
if(c=='t' || c=='u' || c=='v') return '8';
if(c=='w' || c=='x' || c=='y') return '9';
if(c=='o' || c=='q' || c=='z') return '0';
return '0';
}
}

```
This entry was posted in poj. Bookmark the permalink.