`
huntfor
  • 浏览: 201134 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Letter Combinations of a Phone Number

 
阅读更多

新博文地址:[leetcode]Letter Combinations of a Phone Number

新博文中采用了DFS算法,代码简洁易懂

http://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

 这段代码自己看着都感觉恶心。。。。下次再优化吧,不多说,迭代

StringBuilder str = new StringBuilder();
	ArrayList<String> result = new ArrayList<String>();

	public ArrayList<String> letterCombinations(String digits) {
		char[][] charTable = { {}, {}, { 'a', 'b', 'c' }, { 'd', 'e', 'f' },
				{ 'g', 'h', 'i' }, { 'j', 'k', 'l' }, { 'm', 'n', 'o' },
				{ 'p', 'q', 'r', 's' }, { 't', 'u', 'v' },
				{ 'w', 'x', 'y', 'z' } };
		List<Integer> numList = new ArrayList<Integer>();
		for (int i = 0; i < digits.length(); i++) {
			if (digits.charAt(i) > '1') {//这个numList完全没必要,懒得改了
				numList.add(digits.charAt(i) - '0');
			}
		}
		if (numList.isEmpty()) {
			result.add("");//结果为空时,一定要加个空串。。。。何必呢
			return result;
		}
		if (numList.get(0) < 2) {
			return result;
		} else {
			if (numList.size() == 1) {
				for (char tem : charTable[numList.get(0)]) {
					str.append(tem);
					result.add(str.toString());
					str.deleteCharAt(str.length() - 1);
				}
			} else {
				for (char tem : charTable[numList.get(0)]) {
					str.append(tem);
					letterCombinations(digits.substring(1));
					str.deleteCharAt(str.length() - 1);
				}
			}
		}
		return result;
	}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics