Skuteczny algorytm policzyć ewentualnych słów dla sekwencji manipulatora bez T9

głosy
2

disclaimer : Ponieważ istnieje kilka podobnych , ale nie jednakowe pytania, prosimy o zapoznanie się z uwagą, znajdę tylko referencje dla manipulatora z T9, ale nikt bez.

  • Biorąc pod klawiaturę telefonu z literami

2 - a, b, c,

3 - D, E, F

... i tak dalej

  • Biorąc pod uwagę ciąg cyfr numeru, przykład 222

Zapytanie : Znajdź ile to możliwe słowa mogą być pisane bez T9

Przykład:

222 może być:

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

So, 4 możliwe rozwiązania

2222 może być:

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)

So, 7 możliwych rozwiązań

Wymagania:
- brak podejście backtracking / bruteforce
- muszą być skuteczne z długich sekwencji (więcej niż 1000 cyfr, mniej niż 10 sekund, aby wykonać)
- nie ma potrzeby, aby powrócić wszystkie możliwe słowa , ale tylko ich liczbę

Uwaga: Nie szukam dla ostatecznego algorytmu, ale wskazania dotyczące możliwego podejścia

Dzięki

Utwórz 18/12/2018 o 11:08
źródło użytkownik
W innych językach...                            


1 odpowiedzi

głosy
2

wprowadzić opis obrazu tutaj

Algorytm / Intuicja:

  • Jak to oznacza w powyższym obrazie, dla jednej cyfry, są 3-4 możliwości.
  • Jeśli naciśniemy tą samą cyfrą 2 lub 3 lub 4 razy, możemy uzyskać różne znaki na wyświetlaczu.
  • Na przykład, jeśli mamy naciśnij 2
    • 1 raz - a
    • 2 razy - b
    • 3 razy - c
  • Tak więc, gdy obliczamy / policzyć liczbę możliwych podciągów, musimy dodać subproblem(i-2),subproblem(i-3),subproblem(i-4)wartości do naszej ogólnej liczby jeśli zdarza się, że i = i-1 = i-2.
  • Na przykład, weźmy 222 . Będziemy przyjmować odgórnego podejścia.
  • Pierwszy 2 w 222 ma tylko jeden możliwość (który będzie typowania a).
  • Na drugi 2 w 222 , może dać nam albo aczy to może być, że 2został naciśnięty 2 razy dając nam b. Tak więc, kombinacje mogą być aai b.
  • Dla trzeciego 2 do 222 , może być aalbo b(jeśli uruchomić z sekund 2) lub c.
  • Dlatego też nie. kombinacji dla każdego indeksu ijest sumą nie. zapałek z itill i-3lub i-4, w zależności od nr. znaków każda cyfra reprezentuje w manipulatorze.
  • Zauważ, że jeśli ja th charakter meczów i-1, następnie dodamy dp[i-2]a nie dp[i-1]od i-1 till ireprezentuje pojedynczy znak (po naciśnięciu kilka razy).

Kod:

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

Wydajność:

222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
Odpowiedział 18/12/2018 o 12:31
źródło użytkownik

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