Effiziente Algorithmus möglich Worte für eine Tastenkombination zu zählen, ohne T9

stimmen
2

Haftungsausschluss : Da gibt es einige sind ähnlich , aber nicht gleich Fragen, lesen Sie bitte mit Aufmerksamkeit, ich nur Hinweise für die Tastatur mit T9 finden kann, aber niemand ohne.

  • eine Telefontastatur mit Buchstaben gegeben

2 - a, b, c

3 - d, e, f

... und so weiter

  • Bei einer Folge von Nummernziffern, Beispiel 222

Anfrage : Finden Sie, wie viele mögliche Wörter geschrieben werden kann ohne T9

Beispiel:

222 können sein:

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 mögliche Lösungen

2222 können sein:

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 mögliche Lösungen

Anforderungen:
- kein Backtracking / Brute - Force - Ansatz
- müssen mit langen Sequenzen (mehr als 1000 Stellen, weniger als 10 Sekunden ausgeführt werden ) effizient sein
- es gibt keine Notwendigkeit , alle möglichen Wörter zurückkehren , sondern nur ihre Zählung

Bitte beachten Sie: Ich bin für den letzten Algorithmus nicht auf der Suche, aber Hinweise auf den möglichen Ansatz

Vielen Dank

Veröffentlicht am 18/12/2018 um 11:08
quelle vom benutzer
In anderen Sprachen...                            


1 antworten

stimmen
2

Geben Sie hier image description

Algorithmus / Intuition:

  • Wie es in dem obigen Bild, für eine einzelne Ziffer steht, gibt es 3-4 Möglichkeiten.
  • Wenn wir die gleiche Ziffer 2 oder 3 oder 4 Mal drücken, erhalten wir unterschiedliche Zeichen auf dem Display.
  • Wie, wenn wir drücken 2
    • 1 mal - a
    • 2 Mal - b
    • dreimal - c
  • Also, wenn wir berechnen / die Anzahl der möglichen Teil zählen, müssen wir hinzufügen , subproblem(i-2),subproblem(i-3),subproblem(i-4)Werte für unsere Gesamtzahl , wenn es das passiert i = i-1 = i-2.
  • Zum Beispiel, nehmen wir 222 . Wir werden einen Top-Bottom - Ansatz verabschieden.
  • Erste 2 in 222 hat nur 1 Möglichkeit (die wird die Eingabe a).
  • Für die zweiten 2 in 222 , kann es uns entweder geben aoder es könnte sein , dass 2wurde 2 mal gedrückt gibt uns ein b. So können Kombinationen sein aaund b.
  • Für dritte 2 in 222 , kann es sein , aoder b(wenn von den zweiten gestartet 2) oder c.
  • Daher Nr. von Kombinationen für jeden Index iist die Summe von Nr. die Spiele von ibis i-3oder i-4, bei nicht abhängig. jede Ziffer steht in der Tastatur Zeichen.
  • Beachten Sie, dass , wenn ich th Charakter mit übereinstimmt i-1, dann fügen wir dp[i-2]und nicht dp[i-1]da i-1 till irepräsentiert ein einzelnes Zeichen (wenn mehrere Male gedrückt).

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

Ausgabe:

222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
Beantwortet am 18/12/2018 um 12:31
quelle vom benutzer

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