LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Letter Combinations of a Phone Number" 문제입니다.
--> https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
문제 :
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below.
Note that 1 does not map to any letters.
Example 1 :
Input : digits = "23"
Output : ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2 :
Input : digits = ""
Output : []
Example 3 :
Input : digits = "2"
Output : ["a","b","c"]
Constraints :
- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9'].
이 문제는 주어진 숫자 문자열을 사용하여 전화기 키패드의 문자 조합을 모두 반환하는 문제입니다. 예를 들어, 입력이 "23"이면 가능한 문자 조합은 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]입니다. 문자열이 비어있으면 빈 배열을 반환하고, 숫자가 하나인 경우 해당 숫자에 매핑된 문자를 모두 반환합니다.
class Solution {
public List<String> letterCombinations(String digits) {
Map<String, List<String>> digitsMap = new HashMap<>();
digitsMap.put("2", Arrays.asList("a", "b", "c"));
digitsMap.put("3", Arrays.asList("d", "e", "f"));
digitsMap.put("4", Arrays.asList("g", "h", "i"));
digitsMap.put("5", Arrays.asList("j", "k", "l"));
digitsMap.put("6", Arrays.asList("m", "n", "o"));
digitsMap.put("7", Arrays.asList("p", "q", "r", "s"));
digitsMap.put("8", Arrays.asList("t", "u", "v"));
digitsMap.put("9", Arrays.asList("w", "x", "y", "z"));
List<String> res = new ArrayList<>();
if (digits.length() == 0) return res; // Return empty list for empty input
letterCombinationsHelper(digitsMap, digits, 0, "", res);
return res;
}
private static void letterCombinationsHelper(Map<String, List<String>> digitsMap, String digits, int index, String comb, List<String> res) {
if (index == digits.length()) {
res.add(comb);
return;
}
String digit = String.valueOf(digits.charAt(index));
if (digitsMap.containsKey(digit)) {
for (String letter : digitsMap.get(digit)) {
letterCombinationsHelper(digitsMap, digits, index + 1, comb + letter, res);
}
}
}
}
이 코드는 딱 한 눈에 봐도 아주 효율적이진 못해 보입니다. 아무래도 초반에 일일이 매핑하는 게 시간을 많이 까먹게 생겼죠. 그래도 제 코드를 설명드리겠습니다 :
- 맵 초기화:
- 전화기 키패드의 숫자와 문자들을 매핑하는 맵을 초기화합니다.
- 결과 리스트 초기화 및 입력 검증:
- 결과를 저장할 리스트를 초기화합니다.
- 입력 문자열이 비어있으면 빈 리스트를 반환합니다.
- 재귀 함수 호출:
- 재귀 함수를 호출하여 가능한 모든 문자 조합을 생성합니다.
- 재귀 함수 정의:
- 현재 인덱스가 입력 문자열의 길이와 같으면 현재 조합을 결과 리스트에 추가합니다.
- 현재 숫자의 문자를 가져와서 각 문자를 순회하면서 재귀적으로 다음 조합을 생성합니다.
시간 및 공간 복잡도:
- 시간 복잡도:
- 각 숫자가 최대 4개의 문자로 매핑되므로, 모든 조합을 생성하는 시간 복잡도는 O(4^n)입니다. 여기서 n은 입력 문자열의 길이입니다.
- 공간 복잡도:
- 재귀 호출 스택의 깊이는 입력 문자열의 길이 n에 비례합니다.
- 결과 리스트의 크기는 생성된 모든 조합의 수에 비례합니다.
- 따라서 공간 복잡도는 O(n)입니다.
그래서 제가 다른 유저들의 모범답안을 하나 인용해 오겠습니다 :
class Solution {
List<String> res = null;
String [] strMap = {"0","1","abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
res = new ArrayList<>();
if(digits.length() == 0){
return res;
}
dfs(0,digits,new StringBuilder());
return res;
}
void dfs(int length ,String digits,StringBuilder temp){
if(length == digits.length()){
res.add(temp.toString());
return;
}
char ch = digits.charAt(length);
String str = strMap[ch -'0'];
for(char c:str.toCharArray()){
temp.append(c);
dfs(length+1,digits,temp);
temp.deleteCharAt(temp.length()-1);
}
}
}
백 트래킹을 잘 이용한 코드입니다.
'LeetCode' 카테고리의 다른 글
[LeetCode] - 78. Subsets (0) | 2024.07.25 |
---|---|
[LeetCode] - 73. Set Matrix Zeroes (0) | 2024.07.25 |
[LeetCode] - 3120. Count the Number of Special Characters (2) | 2024.07.24 |
[LeetCode] - 4. Median of Two Sorted Arrays (2) | 2024.07.24 |
[LeetCode] - 20. Valid Parentheses (0) | 2024.07.24 |