[LeetCode 17] Letter Combinations of a Phone Number with JAVA

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

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 digit 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'].

 

import java.util.*;

public class Solution {
    static String[] phone = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    static List<String> ans;
    public List<String> letterCombinations(String digits) {
        ans = new LinkedList<>();
        if (digits.equals("")) return ans;
        StringBuilder sb = new StringBuilder();
        dfs(0, digits, sb);
        return ans;
    }
    public void dfs(int depth, String digits, StringBuilder sb){
        if (depth == digits.length()){
            ans.add(sb.toString());
            return;
        }
        int pos = digits.charAt(depth) - '2';
        String text = phone[pos];
        int n = text.length();
        for (int i = 0; i < n; i++){
            sb.append(text.charAt(i));
            dfs(depth + 1, digits, sb);
            sb.setLength(sb.length() - 1);
        }
    }
}

1. 어려웠던 점:

- 알고리즘 문제풀이를 처음 공부할 때는 풀지 못했는데 이제 이 정도 문제는 쉽게 풀 수 있게 되었다.

 

2. 알게된 점:

- 백트래킹 복습

 

3. 알고리즘 풀이:

- phone 배열에 각 경우에 해당하는 스트링을 저장해준다.

이 때, 인덱스 0에 해당하는 값은 '2'에 해당하는 값이므로

입력값에 - '2'를 해줘 해당하는 인덱스를 찾아가도록 해준다.

 

원하는 문자열의 길이가 되면 그동안 완성된 String을 링크드리스트에 넣어준다.

아주 기본적인 백트래킹 문제이다.