algoritmo eficiente para contar palavras possíveis para uma seqüência de teclado, sem T9

votos
2

aviso : uma vez que existem algumas semelhantes , mas não iguais perguntas, por favor leia com atenção, eu posso encontrar somente referências para teclado com T9, mas ninguém sem.

  • Dado um teclado do telefone com letras

2 - a, b, c

3 - d, e, f

... e assim por diante

  • Dada uma sequência de dígitos de um número, o exemplo 222

Pedido : Encontre quantas palavras possíveis podem ser escritas sem T9

Exemplo:

222 pode ser:

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

Assim, 4 soluções possíveis

2222 pode 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)

Então, 7 soluções possíveis

Requisitos:
- nenhuma abordagem retrocesso / bruteforce
- deve ser eficiente com sequências longas (mais de 1000 dígitos, menos de 10 segundos para executar)
- não há necessidade de voltar todas as palavras possíveis , mas apenas a sua contagem

Por favor, note: Eu não estou olhando para o algoritmo final, mas as indicações sobre a abordagem possível

obrigado

Publicado 18/12/2018 em 11:08
fonte usuário
Em outras línguas...                            


1 respostas

votos
2

digite descrição da imagem aqui

Algoritmo / Intuição:

  • Como se representa na imagem de cima, para um único dígito, existem possibilidades 3-4.
  • Se pressionar o mesmo dígito 2 ou 3 ou 4 vezes, temos diferentes personagens na tela.
  • Como, se nós pressionamos 2
    • 1 vez - a
    • 2 vezes - b
    • Três vezes - c
  • Então, quando calculamos / contar o número de possíveis substrings, precisamos adicionar subproblem(i-2),subproblem(i-3),subproblem(i-4)valores à nossa contagem total se acontece que i = i-1 = i-2.
  • Por exemplo, vamos dar 222 . Vamos adotar uma abordagem de cima para baixo.
  • Primeiro 2 em 222 tem apenas uma possibilidade (que será a digitação a).
  • Para a segunda 2 em 222 , ele pode nos dar tanto aou pode ser que 2foi pressionado 2 vezes nos um dando b. Assim, as combinações podem ser aae b.
  • Para terceiro 2 em 222 , que pode ser aou b(se iniciado a partir de segundo 2) ou c.
  • Por isso, não. de combinações para cada índice ié a soma de n. de fósforos de iaté i-3ou i-4, dependendo não. caracteres de cada dígito representa no teclado.
  • Note que se i th caracteres combina com i-1, então nós adicionamos dp[i-2]e não dp[i-1]desde i-1 till irepresenta um único caractere (quando pressionado várias vezes).

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));
        }
    }
}

Saída:

222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
Respondeu 18/12/2018 em 12:31
fonte usuário

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