leetcode上样例通过,提交却通不过,来牛客上试了一下没有问题。dfs
public class Solution {
public static HashMap<Integer, String> mp = new HashMap<>();
public ArrayList<String> phoneNumber (String digits) {
// write code here
String cur = "";
ArrayList<String> ans = new ArrayList<>();
//空字符串返回空ans
if (digits.length() == 0)return ans;
//添加数字-字符串映射
for (int i = 0; i < 26; i++) {
Character temp = (char)('a' + i);
int num = i / 3 + 2;
if (num > 7) {
num = (i - 1) / 3 + 2;
}
if (num > 9) {
num = (i - 2) / 3 + 2;
}
String chars = mp.getOrDefault(num, "");
chars += temp.toString();
mp.put(num, chars);
}
//深度优先搜索
dfs(digits, 0, cur, ans);
return ans;
}
//dfs
public void dfs(String s, int pos, String cur, List<String> ans) {
//位置变量pos超出长度,添加结果cur到ans,返回
if (pos == s.length()) {
ans.add(new String(cur));
return;
}
//下一层,回溯
for (Character temp : mp.get(s.charAt(pos) - '0').toCharArray()) {
cur += temp.toString();
dfs(s, pos + 1, cur, ans);
cur = cur.substring(0, cur.length() - 1);
}
return;
}
}