LeetCode – Combinaciones de letras de un número de teléfono (Java)

Dada una cadena de dígitos, devuelve todas las combinaciones de letras posibles que el número podría representar. (Revise su teléfono celular para ver las asignaciones) Entrada: Cadena de dígitos «23», Salida: [«ad», «ae», «af», «bd», «be», «bf», «cd», «ce», «cf»].

Solución Java 1 – DFS

Este problema puede resolverse mediante un algoritmo DFS típico. Los problemas de DFS son muy similares y se pueden resolver mediante una recursividad simple.

public List<String> letterCombinations(String digits) {
    HashMap<Character, char[]> dict = new HashMap<Character, char[]>();
    dict.put('2',new char[]{'a','b','c'});
    dict.put('3',new char[]{'d','e','f'});
    dict.put('4',new char[]{'g','h','i'});
    dict.put('5',new char[]{'j','k','l'});
    dict.put('6',new char[]{'m','n','o'});
    dict.put('7',new char[]{'p','q','r','s'});
    dict.put('8',new char[]{'t','u','v'});
    dict.put('9',new char[]{'w','x','y','z'});
 
    List<String> result = new ArrayList<String>();
    if(digits==null||digits.length()==0){
        return result;
    }
 
    char[] arr = new char[digits.length()];
    helper(digits, 0, dict, result, arr);
 
    return result;
}
 
private void helper(String digits, int index, HashMap<Character, char[]> dict, 
                        List<String> result, char[] arr){
    if(index==digits.length()){
        result.add(new String(arr));
        return;
    }
 
    char number = digits.charAt(index);
    char[] candidates = dict.get(number);
    for(int i=0; i<candidates.length; i++){
        arr[index]=candidates[i];
        helper(digits, index+1, dict, result, arr);
    }
}

LeetCode - Diseño de directorio telefónico (Java)

La complejidad del tiempo es O (k ^ n), donde k es el mayor número de letras que un dígito puede mapear (k = 4) y n es la longitud de la cadena de dígitos.

Solución Java 2 – BFS

public List<String> letterCombinations(String digits) {
    HashMap<Character, String> map = new HashMap<>();
    map.put('2', "abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");
 
    List<String> l = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return l;
    }
 
    l.add("");
 
    for (int i = 0; i < digits.length(); i++) {
        ArrayList<String> temp = new ArrayList<>();
        String option = map.get(digits.charAt(i));
 
        for (int j = 0; j < l.size(); j++) {
            for (int p = 0; p < option.length(); p++) {
                temp.add(new StringBuilder(l.get(j)).append(option.charAt(p)).toString());
            }
        }
 
        l.clear();
        l.addAll(temp);
    }
 
    return l;
}

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta