[LeetCode] 17. Letter Combinations of a Phone Number

轉自LeetCode

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"].

<Solution>

這題簡單來說，就是根據 input 的長度去排列組合

例如 input 是 "234"，那 output 會是 "adg"、"adh"、"adi"、"aeg"等

從這邊可以看出，可以用DFS來做這件事

code 如下

	class Solution {
	public:
	vector<string> letterCombinations(string digits) {
	vector<string> ans;
	if(digits.length() == 0) {
	return ans;
	}
	//> dictionary for each digit
	string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
	dfs("", dict, 0, digits, ans);
	return ans;
	}
	//> dfs algorithm
	void dfs(string permutation, string *dict, const int & index, const string &digits, vector<string> &ans) {
	//> reach the end
	if(index == digits.length()) {
	ans.push_back(permutation);
	return;
	}
	string dictStr = dict[digits[index] - '2'];
	for(int i = 0; i < dictStr.length(); i++) {
	dfs(permutation+dictStr[i], dict, index + 1, digits, ans);
	}
	}
	};

view raw letterCombination.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	private val ans = mutableListOf<String>()
	fun letterCombinations(digits: String): List<String> {
	return if (digits.isEmpty()) {
	ans
	} else {
	val dict = listOf("abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
	dfs(0, digits, dict, "")
	ans
	}
	}
	fun dfs(start: Int, digits: String, dict: List<String>, cmb: String) {
	if (cmb.length == digits.length) {
	ans.add(cmb)
	return
	}
	val str = dict[digits[start] - '2']
	for(i in str.indices) {
	dfs(start+1, digits, dict, cmb + str[i])
	}
	}
	}

view raw letter_combinations_of_a_phone_number.kt hosted with ❤ by GitHub