algorithme efficace pour compter les mots possibles pour une séquence de touches, sans T9

voix
2

Avertissement : car il existe des similaires mais pas égales des questions, s'il vous plaît lire attentivement, je peux trouver que des références pour clavier avec T9, mais pas l' autre sans.

  • Compte tenu d'un clavier de téléphone avec des lettres

2 - a, b, c

3 - d, e, f

... etc

  • Compte tenu d'une séquence de chiffres du numéro, par exemple 222

Demande : Trouver combien de mots possibles peuvent être écrits sans T9

Exemple:

222 peuvent être:

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

Ainsi, 4 solutions possibles

2222 peut être:

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)

Ainsi, 7 solutions possibles

Exigences:
- pas d' approche retours en arrière / bruteforce
- doivent être efficaces avec des séquences longues (plus de 1000 chiffres, moins de 10 secondes pour exécuter)
- il n'y a pas besoin de retourner tous les mots possibles , mais seulement leur nombre

S'il vous plaît noter: Je ne suis pas à la recherche de l'algorithme final, mais des indications sur l'approche possible

Merci

Créé 18/12/2018 à 11:08
source utilisateur
Dans d'autres langues...                            


1 réponses

voix
2

entrez la description d'image ici

Algorithme / Intuition:

  • Comme il représente dans l'image ci-dessus, pour un seul chiffre, il y a 3-4 possibilités.
  • Si on appuie sur le même chiffre 2 ou 3 ou 4 fois, nous obtenons différents caractères sur l'écran.
  • Comme, si nous pressons 2
    • Une fois - a
    • 2 fois - b
    • 3 fois - c
  • Donc, quand on calcule / compter le nombre de sous - chaînes possibles, nous devons ajouter des subproblem(i-2),subproblem(i-3),subproblem(i-4)valeurs à notre nombre total s'il arrive i = i-1 = i-2.
  • Par exemple, nous allons prendre 222 . Nous allons adopter une approche de haut en bas.
  • Tout d' abord 2 à 222 a seulement 1 possibilité (qui sera taper a).
  • Pour la deuxième 2 à 222 , il peut nous donner une ou l' autre aou peut - être que 2a été pressé 2 fois nous donner un b. Ainsi, des combinaisons peuvent être aaet b.
  • Pour la troisième 2 en 222 , il peut être aou b(si commencé de seconde 2) ou c.
  • Par conséquent, non. des combinaisons pour chaque indice iest somme non. des matchs de itill i-3ou i-4, selon pas. de caractères chaque chiffre représente dans le clavier.
  • Notez que si i ième caractère correspond à i-1, puis on ajoute dp[i-2]et non dp[i-1]depuis i-1 till ireprésente un seul caractère (lorsqu'il est pressé plusieurs fois).

Code:

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

Sortie:

222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
Créé 18/12/2018 à 12:31
source utilisateur

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