Letter Combinations of a Phone Number leetcode - Ryan的修炼之路

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

回溯法

说明

1. 返回条件： 当所得到的string长度与给入的string digits长度相同时候

2. 传入参数: 用一个数来记录string的长度, 每次递归传入长度+1和新的string

复杂度

假设有k个digit 每个digit可以代表m个字符, 时间O(m^k) 空间O(m^k)

代码

public List<String> letterCombinations(String digits) {    List<String> res = new ArrayList<String>();    if (digits == null || digits.length() == 0) {        return res;    }    String[] map= {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};    StringBuilder tem = new StringBuilder();    helper(res, tem, digits, 0, map);    return res;}public void helper(List<String> res, StringBuilder tem, String digits, int index, String[] map) {    if (index == digits.length()) {        res.add(tem.toString());        return;    }    int m = digits.charAt(index) - '0';    for (int i = 0; i < map[m].length(); i++) {        tem.append(map[m].charAt(i));        helper(res, tem, digits, index + 1, map);        tem.deleteCharAt(tem.length() - 1);    }}