首页 > 数据结构 > Hash表 > POJ 1732 Phone numbers [解题报告] Java
2013
11-10

POJ 1732 Phone numbers [解题报告] Java

Phone numbers

问题描述 :

In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to member such a kind of numbers. One method how to do it in an easy way is to assign letters to digits as shown in the following picture:


1 ij 2 abc 3 def
4 gh 5 kl 6 mn
7 prs 8 tuv 9 wxy
0 oqz



This way every word or a group of words can be assigned a unique number, so you can remember words instead of call numbers. It is evident that it has its own charm if it is possible to find some simple relationship between the word and the person itself. So you can earn that the call number 941837296 of a chess playing friend of yours can be read as WHITEPAWN, and the call number 2855304 of your favourite teacher is read BULLDOG.

Write a program to find the shortest sequence of words (i.e. one having the smallest possible number of words) which corresponds to a given number and a given list of words. The correspondence is described by the picture above.

输入:

The first line of input contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input doesn’t exceed 300KB.

输出:

The only line of output contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text `No solution.’. If there are more solutions having the minimum number of words, you can choose any single one of them.

样例输入:

7325189087
5
it
your
reality
real
our

样例输出:

reality our

解题代码:

//* @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';
	}
}

  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示