3327683_ac_1750ms_7320k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String [] args)	throws IOException
	{
		new Main().run();
	}

	static int [] key = new int [256];

	class Words implements Comparable <Words>
	{
		String number, word;
		int length;

		Words(String str)
		{
			word = str;
			length = str.length();
			number = transform(str);
		}

		public int compareTo(Words that)
		{
			return number.compareTo(that.number);
		}
	}

	static
	{
		key['i'] = key['j'] = '1';
		key['a'] = key['b'] = key['c'] = '2';
		key['d'] = key['e'] = key['f'] = '3';
		key['g'] = key['h'] = '4';
		key['k'] = key['l'] = '5';
		key['m'] = key['n'] = '6';
		key['r'] = key['p'] = key['s'] = '7';
		key['t'] = key['u'] = key['v'] = '8';
		key['w'] = key['x'] = key['y'] = '9';
		key['o'] = key['q'] = key['z'] = '0';
	}

	public void run()	throws IOException
	{
		BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
		String num;
		int no;
		Words [] words;
		int [] best;
		int [] prev;
		int [] st = new int [12];
		int [] ed = new int [12];

		num = in.readLine();
		no = Integer.parseInt(in.readLine());
		words = new Words [no];

		for (int i = 0; i < no; i++)
		{
			words[i] = new Words(in.readLine());
		}

		Arrays.sort(words);

		for (int i = no-1; i >= 0; i--)
		{
			st[words[i].number.charAt(0)-'0'] = i;
		}
		for (int i = 0; i < no; i++)
		{
			ed[words[i].number.charAt(0)-'0'] = i;
		}

		int len = num.length();
		best = new int [len+1];
		prev = new int [len+1];

		Arrays.fill(best,-1);
		best[0] = 0;
		for (int i = 1; i <= len; i++)
		{
			if (best[i-1]==-1)
			{
				continue;
			}
			for (int j = st[num.charAt(i-1)-'0']; j <= ed[num.charAt(i-1)-'0']; j++)
			{
				int l = i + words[j].length - 1;
				if (l > len)
				{
					continue;
				}
				if (words[j].number.equals(num.substring(i-1,l)))
				{
					if (best[l]==-1||best[l]>best[i-1]+1)
					{
						best[l] = best[i-1]+1;
						prev[l] = j;
					}
				}
			}
		}
		if (best[len]==-1)
		{
			System.out.println("No solution.");
		}
		else
		{
			int [] ans = new int [best[len]];
			int l = len;
			int cnt = 0;
			while (l!=0)
			{
				ans[cnt++] = prev[l];
				l -= words[prev[l]].length;
			}
			for (int i = cnt - 1; i >= 0; i--)
			{
				System.out.print(words[ans[i]].word+" ");
			}
			System.out.println();
		}
	}

	public String transform(String str)
	{
		String ret = "";

		for (int i = 0; i < str.length(); i++)
		{
			ret += (char)key[str.charAt(i)];
		}
		return ret;
	}
}