Java ArrayList para imprimir todas las palabras posibles de los dígitos del teléfono

Dado el teclado de un móvil y las teclas que deben presionarse, la tarea es imprimir todas las palabras que se pueden generar presionando estos números.
 

Ejemplos: 
 

Input: str = "12" 
Output: [ad, bd, cd, ae, be, ce, af, bf, cf]
Explanation: The characters that can be formed
by pressing 1 is a, b, c and by pressing 2 characters
d, e, f can be formed.
So all the words will be a combination where first 
character belongs to a, b, c and 2nd character belongs
to d, e, f
 
Input: str = "4"
Output: [j, k, l]
Explanation: The characters that can be formed
by pressing 4 is j, k, l

Método 1 : aquí se analiza otro enfoque Imprima todas las palabras posibles de los dígitos del teléfono
Método 2 :  
Enfoque: El enfoque es ligeramente diferente del enfoque en el otro artículo. Supongamos que hay n teclas que se presionan (a1 a2 a3 ..an). Encuentra todas las palabras que se pueden formar usando (a2 a3 ..an). Suponga que se pueden generar 3 caracteres presionando a1 y luego, para cada carácter, concatene el carácter antes de todas las palabras e insértelos en la lista.
Por ejemplo: 
 

Si la pulsación de tecla es 12 
Los caracteres que se pueden formar pulsando 1 son a, b, cy pulsando 2 se pueden formar los caracteres d, e, f. 
Entonces, todas las palabras que se pueden formar usando 2 son [d, e, f] 
Entonces ahora concatene ‘a’ con todas las palabras devueltas, la lista es [ad, ae, af] de manera similar concatene b y c. Entonces la lista se convierte en [ad, ae, af, bd, be, bf, cd, ce, cf].

Algoritmo: 
 

1. Escriba una función recursiva que acepte la string de pulsación de teclas y devuelva todas las palabras que se pueden formar en una lista de array .
2. Si la longitud de la string dada es 0, devuelva Arraylist que contiene una string vacía.
3. De lo contrario, llame recursivamente a la función con una string excepto el primer carácter de la string original, es decir, una string que contiene todos los caracteres del índice 1 a n-1. y almacene la lista de arreglos devuelta, enumere y cree una nueva lista de arreglos y
4. Obtenga el conjunto de caracteres del primer carácter de la string original, CSet
5. Para cada palabra de la lista , ejecute un bucle a través de Cset y concatene el carácter de Cset delante de la palabra de la lista e insértelos en la lista de arreglos ans .
6. Devuelve la lista de arreglos, y .

Implementación: 
 

// Java implementation of the approach
import java.util.ArrayList;
 
public class GFG {
 
    // String array to store keypad characters
    static final String codes[]
        = { " ", "abc", "def",
            "ghi", "jkl", "mno",
            "pqr", "stu", "vwx",
            "yz" };
 
    // Function that returns an Arraylist
    // which contains all the generated words
    public static ArrayList<String> printKeyWords(String str)
    {
 
        // If str is empty
        if (str.length() == 0) {
            ArrayList<String> baseRes = new ArrayList<>();
            baseRes.add("");
 
            // Return an Arraylist containing
            // empty string
            return baseRes;
        }
 
        // First character of str
        char ch = str.charAt(0);
 
        // Rest of the characters of str
        String restStr = str.substring(1);
 
        ArrayList<String> prevRes = printKeyWords(restStr);
        ArrayList<String> Res = new ArrayList<>();
 
        String code = codes[ch - '0'];
 
        for (String val : prevRes) {
 
            for (int i = 0; i < code.length(); i++) {
                Res.add(code.charAt(i) + val);
            }
        }
        return Res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "23";
 
        // Print all the possible words
        System.out.println(printKeyWords(str));
    }
}

[dg, eg, fg, dh, eh, fh, di, ei, fi]

Análisis de Complejidad: 
 

• Complejidad temporal: O(3 ⁿ ). 
  Aunque la función recursiva se ejecuta n veces. Pero el tamaño de la lista de arreglos crece exponencialmente. Entonces habrá alrededor de 3 ⁿ elementos en la lista de arreglos. Por lo tanto, atravesarlos tomará 3 ⁿ de tiempo.
• Complejidad espacial: O(3 ⁿ ). 
  El espacio requerido para almacenar todas las palabras es O(3 ⁿ ). Como habrá alrededor de 3 ⁿ palabras en la salida.