alle möglichen Kombinationen von einer String-Darstellung einer Zahl

Question

eine Zuordnung Gegeben:

A: 1 
B: 2 
C: 3 
... 
... 
... 
Z: 26 

Suche alle Möglichkeiten, eine Zahl dargestellt werden kann. Z.B. Für eine Eingabe: „121“, können wir es darstellen als:

ABA [using: 1 2 1] 
LA [using: 12 1] 
AU [using: 1 21] 

Ich denke versucht, über irgendeine Art eines dynamischen Programmieransatz, aber ich bin nicht sicher, wie es weitergeht. Diese Frage wurde mir in einem technischen Interview gestellt.

Hier ist eine Lösung, die ich denken konnte, lassen Sie es mich wissen, ob dies gut aussieht: [? Bin ich etwas fehlt]

A[i]: Total number of ways to represent the sub-array number[0..i-1] using the integer to alphabet mapping. 

Lösung:

A[0] = 1 // there is only 1 way to represent the subarray consisting of only 1 number 
for(i = 1:A.size): 
    A[i] = A[i-1] 
    if(input[i-1]*10 + input[i] < 26): 
     A[i] += 1 
    end 
end 
print A[A.size-1] 

Answer 1

Um nur die Zählung zu erhalten, die dynamische Programmierung Ansatz ziemlich geradlinig ist:

A[0] = 1 
for i = 1:n 
    A[i] = 0 
    if input[i-1] > 0       // avoid 0 
    A[i] += A[i-1]; 
    if i > 1 &&       // avoid index-out-of-bounds on i = 1 
     10 <= (10*input[i-2] + input[i-1]) <= 26 // check that number is 10-26 
    A[i] += A[i-2]; 

Wenn Sie stattdessen alle Darstellungen auflisten möchten, dynamische Programmierung für diese nicht besonders gut geeignet ist, Sie‘ besser mit einem einfachen rekursiven Algorithmus.

Answer 2

uns einfach Breite beginn Suche.

etwa 121

Starten von der ersten ganzen Zahl, berücksichtigen 1 ganzzahligen Charakter ersten, Karte 1 a, 21 verlassen dann 2 integer Zeichenübersicht 12 bis L leave 1.

Answer 3

Zunächst einmal, Wir müssen eine intuitive Möglichkeit finden, alle Möglichkeiten aufzuzählen. Meine einfache Konstruktion, ist unten angegeben. Jetzt

let us assume a simple way to represent your integer in string format. 

    a1 a2 a3 a4 ....an, for instance in 121 a1 -> 1 a2 -> 2, a3 -> 1 

,

Wir müssen herausfinden, Anzahl der Möglichkeiten des Vergebens a + zwischen zwei Zeichen unterzeichnen. + bedeutet Zeichenverkettung hier.

a1 - a2 - a3 - .... - an, - shows the places where '+' can be placed. So, number of positions is n - 1, where n is the string length. 

eine Position einnehmen kann oder auch nicht ein Symbol + haben soll als Bit dargestellt werden. Also, es läuft darauf hinaus, wie viele verschiedene Bit-Strings mit der Länge von n-1 möglich sind, was eindeutig 2^(n-1) ist. Nun, um die Möglichkeiten gehen durch jede Bitkette und legen Sie rechts + Zeichen in entsprechenden Positionen aufzuzählen, um alle Darstellungen zu erhalten,

Für Ihr Beispiel 121

Four bit strings are possible 00 01 10 11 
    1 2 1 
    1 2 + 1 
    1 + 2 1 
    1 + 2 + 1 

    And if you see a character followed by a +, just add the next char with the current one and do it sequentially to get the representation, 

x + y z a + b + c d 

would be (x+y) z (a+b+c) d 

Hoffe, es hilft.

Und Sie müssen auf Edge Fällen kümmern, wo die Größe einer ganzen Zahl> 26, natürlich.

Answer 4

Ich denke, rekursive Traverse durch alle möglichen Kombinationen ganz gut tun würde: Sie müssen nur zählen die Anzahl der Kombinationen

mapping = {"1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G", 
"8":"H", "9":"I", "10":"J", 
"11":"K", "12":"L", "13":"M", "14":"N", "15":"O", "16":"P", 
"17":"Q", "18":"R", "19":"S", "20":"T", "21":"U", "22":"V", "23":"W", 
"24":"A", "25":"Y", "26":"Z"} 

def represent(A, B): 
    if A == B == '': 
     return [""] 
    ret = [] 
    if A in mapping: 
     ret += [mapping[A] + r for r in represent(B, '')] 
    if len(A) > 1: 
     ret += represent(A[:-1], A[-1]+B) 
    return ret 

print represent("121", "") 

Answer 5

Unter der Annahme.

Unter der Annahme, 0 mit einer ganzen Zahl in gefolgt [1,9] ist nicht eine gültige Verknüpfungs, dann eine Brute-Force-Strategie sei:

Count(s,n) 
    x=0 
    if (s[n-1] is valid) 
     x=Count(s,n-1) 
    y=0 
    if (s[n-2] concat s[n-1] is valid) 
     y=Count(s,n-2) 
    return x+y 

Eine bessere Strategie wäre die Verwendung Divide-and-Conquer :

Count(s,start,n) 
    if (len is even) 
    { 
     //split s into equal left and right part, total count is left count multiply right count 
     x=Count(s,start,n/2) + Count(s,start+n/2,n/2); 
     y=0; 
     if (s[start+len/2-1] concat s[start+len/2] is valid) 
     { 
      //if middle two charaters concatenation is valid 
      //count left of the middle two characters 
      //count right of the middle two characters 
      //multiply the two counts and add to existing count 
      y=Count(s,start,len/2-1)*Count(s,start+len/2+1,len/2-1); 
     } 
     return x+y; 
    } 
    else 
    { 
     //there are three cases here: 

     //case 1: if middle character is valid, 
     //then count everything to the left of the middle character, 
     //count everything to the right of the middle character, 
     //multiply the two, assign to x 
     x=... 

     //case 2: if middle character concatenates the one to the left is valid, 
     //then count everything to the left of these two characters 
     //count everything to the right of these two characters 
     //multiply the two, assign to y 
     y=... 

     //case 3: if middle character concatenates the one to the right is valid, 
     //then count everything to the left of these two characters 
     //count everything to the right of these two characters 
     //multiply the two, assign to z 
     z=... 

     return x+y+z; 
    } 

Die Brute-Force-Lösung hat Zeitkomplexität von T(n)=T(n-1)+T(n-2)+O(1) die exponentiell ist.

Die Teile-und-herrsche-Lösung hat eine Zeitkomplexität von T(n)=3T(n/2)+O(1), was O (n ** lg3) ist.

Hoffe, das ist richtig.

Answer 6

So ähnlich?

Haskell Code:

import qualified Data.Map as M 
import Data.Maybe (fromJust) 

combs str = f str [] where 
    charMap = M.fromList $ zip (map show [1..]) ['A'..'Z'] 
    f []  result = [reverse result] 
    f (x:xs) result 
    | null xs = 
     case M.lookup [x] charMap of 
      Nothing -> ["The character " ++ [x] ++ " is not in the map."] 
      Just a -> [reverse $ a:result] 
    | otherwise = 
     case M.lookup [x,head xs] charMap of 
      Just a -> f (tail xs) (a:result) 
       ++ (f xs ((fromJust $ M.lookup [x] charMap):result)) 
      Nothing -> case M.lookup [x] charMap of 
         Nothing -> ["The character " ++ [x] 
           ++ " is not in the map."] 
         Just a -> f xs (a:result) 

Ausgang:

*Main> combs "121" 
["LA","AU","ABA"] 

Answer 7

Hier ist die Lösung hier auf Grund meiner Diskussion:

private static int decoder2(int[] input) { 
    int[] A = new int[input.length + 1]; 
    A[0] = 1; 

    for(int i=1; i<input.length+1; i++) { 
     A[i] = 0; 
     if(input[i-1] > 0) { 
     A[i] += A[i-1]; 
     } 
     if (i > 1 && (10*input[i-2] + input[i-1]) <= 26) { 
     A[i] += A[i-2]; 
     } 
     System.out.println(A[i]); 
    } 
    return A[input.length]; 
} 

Answer 8

Dieses Problem wurde in o getan werden kann (fib (n + 2)) Zeit mit einem Standard-DP-Algorithmus. Wir haben genau n Subprobleme und Knopf wir können jedes Problem mit Größe i in o (fib (i)) Zeit lösen. Summierung der Reihe ergibt fib (n + 2).

Wenn Sie die Frage sorgfältig betrachten, sehen Sie, dass es eine Fibonacci-Reihe ist. Ich nahm einen Standard-Fibonacci-Code und änderte ihn einfach, um unseren Bedingungen zu entsprechen.

Der Raum ist offensichtlich an die Größe aller Lösungen gebunden o (fib (n)).

Betrachten Sie diese Pseudo-Code:

Map<Integer, String> mapping = new HashMap<Integer, String>(); 

List<String > iterative_fib_sequence(string input) { 
    int length = input.length; 
    if (length <= 1) 
    { 
     if (length==0) 
     { 
      return ""; 
     } 
     else//input is a-j 
     { 
      return mapping.get(input); 
     } 
    } 
    List<String> b = new List<String>(); 
    List<String> a = new List<String>(mapping.get(input.substring(0,0)); 
    List<String> c = new List<String>(); 

    for (int i = 1; i < length; ++i) 
    { 
     int dig2Prefix = input.substring(i-1, i); //Get a letter with 2 digit (k-z) 
     if (mapping.contains(dig2Prefix)) 
     { 
      String word2Prefix = mapping.get(dig2Prefix);   
      foreach (String s in b) 
      { 
       c.Add(s.append(word2Prefix)); 
      } 
     } 

     int dig1Prefix = input.substring(i, i); //Get a letter with 1 digit (a-j) 
     String word1Prefix = mapping.get(dig1Prefix);   
     foreach (String s in a) 
     { 
      c.Add(s.append(word1Prefix)); 
     } 

     b = a; 
     a = c; 
     c = new List<String>(); 
    } 
    return a; 
}