Description

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

1 2abc 3def
4ghi 5jkl 6mno
7pqrs 8tuv 9wxyz

Example:

Input: "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.

来源：leetcode 17 letter combinations of a phone number

Solution

Approach 1

借助加法计算进位的思想，下面是我的解法。我首次提交时并没有注意输入字符串为空的情况，对于输入参数的检查还是太容易忽略了。

vector<string> letterCombinations(string digits) {
    vector<string> ans;
    if (digits.empty()) {
	return ans;
    }

    vector<string> letters {"",  "", "abc", "def", "ghi",
	    "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<int> carry(nums.size(), 0);
    vector<int> nums;
    for (char ch : digits) {
	int n = ch - '0';
	nums.push_back(n);
    }

    do{
	string str;
	for (size_t i=0; i<carry.size(); ++i) {
	    str += letters[nums[i]] [carry[i]];
	}
	ans.push_back(str);

	int c = 1;
	for (int i=carry.size()-1; i >= 0; --i) {
	    int d = carry[i] + c;
	    if (d >= letters[nums[i]].size()) {
		carry[i] = 0;
		c = 1;
	    }
	    else {
		carry[i] = d;
		c = 0;
		break;
	    }
	}

	if ( 1 == c) {
	    break;
	}

    } while (1);

    return ans;
}

我在想的是这个算法的时间复杂度是多少，感觉它的时间复杂度应该是O(n2)。

Approach 2 recursive

使用递归完成字符串的拼接，在每次递归，都会增加一个字符。终止递归的条件是字符串长度达到输入参数的长度。递归方法符合生活中的使用场景，还是比较容易理解的。

class Solution {
    char mMap[8][4] = {
	{'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'},
    };

public:
    vector<string> letterCombinations(string digits) {
	vector<string> result;
	backTrack(digits, result, "", 0);
	return result;
    }

    void backTrack(string &digits, vector<string> &result, string combination, int index) {
	if (index >= digits.length()) {
	    if (combination.empty()) {
		return;
	    }
	    result.push_back(combination);
	    return;
	}
	for (char c : mMap[digits[index] - '2']) {
	    if (c == '#')
		continue;

	    combination += c;
	    backTrack(digits, result, combination, index+1);

	    // 这里为什么要删去最后一个呢？
	    // 因为之前在尾部追加了一个c
	    combination.erase(combination.end() - 1);
	}
    }
};

如何评估递归算法的时间复杂度和空间复杂度呢？

Approach 3 BFS

宽度优先搜索，breadth-first search（BFS）,是一种对树（tree）或图（graph）的遍历算法，下面就是这种算法的解法，代码使用java编写。

public List<String> letterCombinations(String digits) {
    LinkedList<String> ans = new LinkedList<String>();
    if(digits.isEmpty()) {
	return ans;
    }

    String[] mapping = new String[] {"0", "1", "abc", "def",
				     "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    ans.add("");
    for(int i=0; i<digits.length(); i++) {
	int x = Character.getNumericValue(digits.charAt(i));

	while(ans.peek().length() == i) {
	    String t = ans.remove(); // remove是从头部删去一个元素
	    for(char s : mapping[x].toCharArray()) {
		ans.add(t+s); // add是向尾部添加一个元素
	    }
	}
    }
    return ans;
}

下面是另外一种使用BFS算法实现的解法

public List<String> letterCombinations(String digits) {
    LinkedList<String> ans = new LinkedList<String>();
    if(digits.isEmpty()) {
	return ans;
    }
    String[] mapping = new String[] {"0", "1", "abc", "def",
				     "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    ans.add("");
    while(ans.peek().length() != digits.length()){
	String remove = ans.remove();
	String map = mapping[digits.charAt(remove.length())-'0'];
	for(char c: map.toCharArray()){
	    ans.addLast(remove+c);
	}
    }
    return ans;
}