编程之美-电话号码对应英语单词

import java.util.Arrays;

public class NumberToWord {

	/**
	 * 编程之美 电话号码对应英语单词
	 * 题目：
     *  手机上的拨号盘，每个数字都对应一些字母，比如2对应ABC，3对应DEF.........，8对应TUV，9对应WXYZ，
     *  要求对一段数字，输出其代表的所有可能的字母组合，如5869，可能代表JTMW、JTMX...
     *  以下程序用DFS得解，但：
	 *  1、程序中输出的单词，是“字母的组合”而已，并不是有真正含义的英文单词
	 *  2、对于含有0和1的电话号码，认为是不合法的输入（因为按键0和1没有对应任何英文字母）
         *  3、2012-11-05 程序中的DFS递归解法，其实和暴力的For循环效率差不多。。。
	 */
	public static void main(String[] args) {
		NumberToWord data = new NumberToWord("234");
		data.numToWord();
	}
	
	private String phoneNumStr;	//字符串格式的电话号码
	private int[] phoneNum;	//数字格式的电话号码
	private int len;	//电话号码的长度
	private char[] result;		//电话号码代表的一个单词
	private static final String[] LETTERS = { 
		"",	  // 0
		"",   // 1
		"ABC",// 2
		"DEF",// 3
		"GHI",// 4
		"JKL",// 5
		"MNO",// 6
		"PQRS",// 7
		"TUV",// 8
		"WXYZ"// 9
	};
	//每个数字按键有几个字母
	private int[] total = { 0, 0, 3, 3, 3, 3, 3, 4, 3, 4 };
	
	public void numToWord() {
		if (phoneNumStr == null || phoneNumStr.length() == 0) {
			System.out.println("phone number is null or empty!");
			return;
		}
		if (!phoneNumStr.matches("[2-9]+")) {
			System.out.println("invalid phone number:" + phoneNumStr);
			return ;
		}
		init();
		dfs(0);
	}
	
	public void dfs(int level) {
		if (level == len) {
			System.out.println(Arrays.toString(result));
			return;
		}
		int num = phoneNum[level];
		String str = LETTERS[num];
		int size = total[num];
		char[] letters = str.toCharArray();
		for (int i = 0; i < size; i++) {
			result[level] = letters[i];
			dfs(level + 1);
		}
	}

	public NumberToWord(String phoneNumStr) {
		this.phoneNumStr = phoneNumStr;
	}
	
	//change "234"(String) to {2, 3, 4}(int[])
	private void init() {
		int len = phoneNumStr.length();
		this.len = len;
		phoneNum = new int[len];
		result = new char[len];
		char[] letters = phoneNumStr.toCharArray();
		for (int i = 0; i < len; i++) {
			phoneNum[i] = letters[i] - '0';
		}
	}
}

评论

2 楼 neyshule 2012-09-04  

本质上是一个多叉树的先序遍历吧，子树从左到右遍历完就行了。

1 楼 neyshule 2012-09-04