algoritmo eficiente para contar palabras posibles para una secuencia de teclado, sin T9

votos
2

exención de responsabilidad : ya que hay algunas similares pero no iguales preguntas, por favor, lea con atención, no puedo encontrar únicas referencias para teclado con T9, pero ningún otro sin él.

  • Dado un teclado del teléfono con las letras

2 - a, b, c

3 - d, e, f

... y así

  • Dada una secuencia de dígitos de los números, el ejemplo 222

Solicitud : Encontrar el número de palabras posible, se puede escribir sin T9

Ejemplo:

222 pueden ser:

array (size=4)
  0 => string 'C' (length=1)
  1 => string 'AB' (length=2)
  2 => string 'BA' (length=2)
  3 => string 'AAA' (length=3)

Así, 4 soluciones posibles

2222 pueden ser:

array (size=7)
  0 => string 'AC' (length=2)
  1 => string 'BB' (length=2)
  2 => string 'CA' (length=2)
  3 => string 'AAB' (length=3)
  4 => string 'ABA' (length=3)
  5 => string 'BAA' (length=3)
  6 => string 'AAAA' (length=4)

Así, los 7 posibles soluciones

Requisitos:
- hay un enfoque retroceso / bruteforce
- deben ser eficientes con secuencias largas (más de 1000 dígitos, a menos de 10 segundos para ejecutar)
- no hay necesidad de volver todas las palabras posibles , pero sólo su recuento

Tenga en cuenta: No estoy buscando el algoritmo final, pero los indicios sobre la posible enfoque

Gracias

Publicado el 18/12/2018 a las 11:08
fuente por usuario
En otros idiomas...                            


1 respuestas

votos
2

introducir descripción de la imagen aquí

Algoritmo / Intuición:

  • Como se representa en la imagen anterior, por un solo dígito, hay 3-4 posibilidades.
  • Si pulsamos el mismo dígito 2 o 3 o 4 veces, obtenemos diferentes caracteres en la pantalla.
  • Al igual que, si apretamos 2
    • 1 vez - a
    • 2 veces - b
    • 3 veces - c
  • Por lo tanto, cuando calculamos / cuente el número de posibles subseries, tenemos que añadir subproblem(i-2),subproblem(i-3),subproblem(i-4)los valores de nuestra recuento total si sucede que i = i-1 = i-2.
  • Por ejemplo, tomemos 222 . Vamos a adoptar un enfoque de arriba hacia abajo.
  • Primero 2 en 222 sólo tiene 1 posibilidad (que será escribiendo a).
  • Por segundo 2 en 222 , puede darnos ya sea ao podría ser que 2se presiona 2 veces nos da una b. Por lo tanto, las combinaciones pueden ser aay b.
  • Para tercio 2 en 222 , que puede ser ao b(si se inicia a partir de segundo 2) o c.
  • Por lo tanto, no. de combinaciones para cada índice ies de suma no. de partidos, de ihasta i-3o i-4, dependiendo no. personajes de cada dígito representa en el teclado.
  • Tenga en cuenta que si i -ésimo carácter coincide con i-1, a continuación, añadimos dp[i-2]y no dp[i-1]desde i-1 till irepresenta un único carácter (cuando se pulsa varias veces).

Código:

import static java.lang.System.out;
public class Solution{    
    public static int possibleStringCount(String s){
        int len = s.length();
        int[] dp = new int[len];
        dp[0] = 1;// possibility is 1 for a single character
        for(int i=1;i<len;++i){
            int possible_chars_length = numberOfRepresentedCharacters(s.charAt(i)-'0') - 1;// because current character itself counts as 1. 
            dp[i] = 0;
            for(int j=i;j>=0;j--){
                if(i - possible_chars_length > j) break;
                if(s.charAt(i) == s.charAt(j)){
                    if(j-1 > -1){
                        dp[i] += dp[j-1];
                    }else{
                        dp[i] += 1;// if there are no combinations before it, then it represents a single character
                    }
                }
            }
        }

        return dp[len-1];
    }

    private static int numberOfRepresentedCharacters(int digit){
       if(digit == 7 || digit == 9) return 4;
        return 3;// it is assumed that digits are between 2-9 always
    }

    public static void main(String[] args) {
        String[] tests = {
            "222","2233","23456789","54667877","5466","7777","22","7898989899","77779999"
        };

        for(String testcase : tests){
            out.println(testcase + " : " + possibleStringCount(testcase));
        }
    }
}

Salida:

222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
Respondida el 18/12/2018 a las 12:31
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more