Phone Keypad Letter Combinations

/*
 * Problem : Keypad words.
 * Input   : A string of digits.
 * Output  : All words.
 * Approach: Backtracking.
 * Time    : O(4^n * n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: pick a letter for the digit at position index, then move to the next digit.
        static void combine(String digits, int index, StringBuilder current, String[] letters, java.util.List<String> result) {
            // Step 2: Base case. We chose a letter for every digit: save the word.
            if (index == digits.length()) {
                result.add(current.toString());
                return;
            }

            // Step 3: Try each letter of this digit in order. After the recursive call, remove the letter (backtrack).
            String options = letters[digits.charAt(index) - '0'];
            for (int i = 0; i < options.length(); i++) {
                current.append(options.charAt(i));
                combine(digits, index + 1, current, letters, result);
                current.deleteCharAt(current.length() - 1);
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String s) {
        String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        java.util.List<String> result = new java.util.ArrayList<>();
        combine(s.trim(), 0, new StringBuilder(), letters, result);
        return result.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(String.join("\n", solve(s)));
    }
}