https://leetcode.com/problems/letter-combinations-of-a-phone-number/description
Q. 입력된 string digits에 아래와 같은 숫자패드를 입력 할 수 있다.
이 때 출력 가능한 모든 문자 조합을 출력하라.
Solution.
Backtracking의 고전과도 같은 문제.
backtracking의 로직을 그대로 적용하면 된다.
이와는 별개로 backtracking은 실생활의 문제를 푸는데 많은 도움이 될수 있다.
흥미를 가지고 봐야 할 항목.
void letter_helper(map<char, string>& mapData, string digits, string curStr, vector<string>& vOut)
{
if (curStr.size() == digits.size())
{
if(digits.size() > 0) // check only valid string set.
vOut.push_back(curStr);
return;
}
int idx = curStr.size();
string strTarget = mapData[digits.at(idx)];
for (int k = 0; k < strTarget.size(); ++k)
{
curStr += strTarget[k]; // push in
letter_helper(mapData, digits, curStr, vOut);
curStr.erase(curStr.end()-1); // pop out
}
}
vector<string> letterCombinations(string digits)
{
// Build Local data for the key pad.
map<char, string> mapData;
mapData['2'] = "abc";
mapData['3'] = "def";
mapData['4'] = "ghi";
mapData['5'] = "jkl";
mapData['6'] = "mno";
mapData['7'] = "pqrs";
mapData['8'] = "tuv";
mapData['9'] = "wxyz";
vector<string> vOut;
letter_helper(mapData, digits, "", vOut);
return vOut;
}
작은 속도안에서의 순위차는 무시한다.
'Leetcode > LeetCode75' 카테고리의 다른 글
[DP-1D][Easy] 1137.N-th Tribonacci Number (1) | 2024.01.15 |
---|---|
[Backtracking][Medium] 216. Combination Sum III (0) | 2024.01.13 |
[Binary Search][Medium] 875. Koko Eating Bananas (2) | 2024.01.12 |
[Binary Search][Medium] 162. Find Peak Element (1) | 2024.01.11 |
[Binary Search][Medium] 2300. Successful Pairs of Spells and Potions (1) | 2024.01.10 |