AOJ1227 77377

問題リンク 77377

• 概要

携帯電話の文字入力を効率的にしたい。"press"という文字列を出したいとき「77377」と打つだけで済むようにする。
キー入力のシーケンスが与えられたとき、作ることができる文章を全て出力せよ。出力する順番は任意でよい。
ただし、この携帯電話にはN個の単語が登録されており、作れる文字列は登録された単語のみからなるものとする。
N<=100
単語は全て英語の小文字, 単語の長さL 1<=L<=50
キー入力のシーケンスの長さLs 1<=Ls<=300

• 解法

深さ優先探索で解きます。
まず、登録された単語を1〜9のシーケンスに置き換えます。
キー入力のシーケンスを先頭から見ていき、その先頭部分が単語のシーケンスに一致したとき、その単語を打つことができます。その単語を作ったら今のインデックスに単語の長さを加えた箇所から同様の処理をします。シーケンスが空になったら文章が完成するので出力します。

• ソース

import java.util.Scanner;

//77377
public class AOJ1227 {

	int[] ref = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
	int n;
	String[] w, rep;
	String s;
	
	void dfs(int i, String r){
		if(i==s.length()){
			System.out.println(r.substring(1)+"."); return;
		}
		String sub = s.substring(i);
		for(int j=0;j<n;j++){
			if(!sub.startsWith(rep[j]))continue;
			dfs(i+rep[j].length(), r+" "+w[j]);
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			w = new String[n]; rep = new String[n];
			for(int i=0;i<n;i++){
				w[i] = sc.next();
				String res = "";
				for(int j=0;j<w[i].length();j++)res+=ref[w[i].charAt(j)-'a'];
				rep[i] = res;
			}
			s = sc.next();
			dfs(0, "");
			System.out.println("--");
		}
	}
	
	public static void main(String[] args) {
		new AOJ1227().run();
	}
}