Open youngyangyang04 opened 3 months ago
List<String> paths = new ArrayList<>();
StringBuilder path = new StringBuilder();
private String[] letters = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
private void backtracking(String digits, int index){
if(index == digits.length()){
paths.add(path.toString());
return;
}
int num = digits.charAt(index) - '0';
String letter = letters[num];
for(int i = 0; i < letter.length(); i++){
path.append(letter.charAt(i));
backtracking(digits, index + 1);
path.setLength(path.length() - 1);
}
}
// 深度1: backtracking("23", 0), 在 "abc" 中取一个, path = ""
i = 0:path = "a",递归 backtracking("23", 1),回溯,path = ""
i = 1:path = "b",递归 backtracking("23", 1),回溯,path = ""
i = 2:path = "c",递归 backtracking("23", 1),回溯,path = ""
// 深度2: backtracking("23", 1), 在 "def" 中取一个, path = "a"或"b"或"c"
// 例: backtracking("23", 1), 在 "def" 中取一个, path = "a"
i = 0:path = "ad",递归 index 为 2,加入 paths,回溯,path = "a"
i = 1:path = "ae",递归 index 为 2,加入 paths,回溯,path = "a"
i = 2:path = "af",递归 index 为 2,加入 paths,回溯,path = "a"
写不出for循环多想想自己的原因
private:
unordered_map<int, string> phone =
{
{2, "abc"},
{3, "def"},
{4, "ghi"},
{5, "jkl"},
{6, "mno"},
{7, "pqrs"},
{8, "tuv"},
{9, "wxyz"}
};
public:
vector letterCombinations(string digits) {
vector output;
int n = digits.size();
if (n == 0) {
return {};
}
vector mid;
vector ans;
for (int i = 0; i < n; i++) {
int x = digits[i]-'0';
mid.push_back(phone[x]);
}
while (n > 0) {
string s = mid.front();
mid.erase(mid.begin());
if (output.empty()) {
for (char x : s) {
string m; // 不存在这类写法:string m = x
// 因为没有对应的构造函数:
m = x;
output.push_back(m);
}
n--;
continue;
}
for (char x : s) {
for (string y : output) {
ans.push_back(y + x);
}
}
output.assign(ans.begin(), ans.end());
ans.clear();
n--;
}
return output;
}
};
https://www.programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html