Tìm tất cả các kết hợp có thể có của một String đại diện của một số

Question

Với một ánh xạ:

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

Tìm tất cả các cách có thể một số có thể được đại diện. Ví dụ. Đối với một đầu vào: "121", chúng ta có thể đại diện cho nó như:

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

Tôi cố gắng suy nghĩ về việc sử dụng một số loại một cách tiếp cận lập trình năng động, nhưng tôi không chắc chắn làm thế nào để tiến hành. Tôi đã được hỏi câu hỏi này trong một cuộc phỏng vấn kỹ thuật.

Dưới đây là một giải pháp tôi có thể nghĩ ra, xin vui lòng cho tôi biết nếu điều này có vẻ tốt: [? Tôi thiếu một cái gì đó]

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

Giải pháp:

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

Để chỉ lấy số liệu, phương pháp quy hoạch động là khá thẳng về phía trước:

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]; 

Nếu bạn thay vì muốn liệt kê tất cả cơ quan đại diện, lập trình năng động không phải là đặc biệt rất phù hợp cho điều này, bạn' tốt hơn với một thuật toán đệ quy đơn giản.

Answer 2

Chỉ cần chúng ta theo chiều rộng đầu tiên Tìm kiếm.

ví dụ 121

Bắt đầu từ số nguyên đầu tiên, xem xét 1 số nguyên nhân vật đầu tiên, bản đồ từ 1 tới một, để lại 21 sau đó 2 số nguyên đồ vật từ 12 đến L nghỉ 1.

Answer 3

Trước hết, chúng ta cần tìm một cách trực quan để liệt kê tất cả các khả năng. Xây dựng đơn giản của tôi, được đưa ra dưới đây.

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 

Bây giờ,

Chúng ta cần phải tìm ra số khả năng đặt một dấu + ở giữa hai nhân vật. + là có nghĩa là ký tự nối ở đây.

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

Giả sử vị trí có thể có hoặc không có ký hiệu + sẽ được biểu diễn dưới dạng bit. Vì vậy, điều này sẽ tóm tắt bao nhiêu chuỗi bit khác nhau có thể với độ dài của n-1, rõ ràng là 2^(n-1). Bây giờ để liệt kê các khả năng đi qua tất cả các chuỗi bit và đặt dấu + ngay ở các vị trí tương ứng để có được tất cả các cơ quan đại diện,

Ví dụ của bạn, 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 

Hy vọng nó giúp.

Và bạn sẽ phải chăm sóc các trường hợp cạnh mà kích thước của một số số nguyên> 26, tất nhiên.

Answer 4

Tôi nghĩ rằng, traverse đệ quy qua tất cả kết hợp có thể sẽ làm tốt:

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

Giả sử bạn chỉ cần đếm số kết hợp.

Giả sử 0 tiếp theo là một số nguyên trong [1,9] là không phải là một nối hợp lệ, sau đó một chiến lược brute-force sẽ là:

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 

Một chiến lược tốt hơn là nên sử dụng chia-và-chinh phục :

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

Giải pháp brute-force có độ phức tạp thời gian là T(n)=T(n-1)+T(n-2)+O(1) là theo cấp số mũ.

Giải pháp phân chia và chinh phục có độ phức tạp thời gian là T(n)=3T(n/2)+O(1) là O (n ** lg3).

Hy vọng điều này là chính xác.

Answer 6

Một cái gì đó như thế này? đang

Haskell:

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) 

Output:

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

Answer 7

Dưới đây là giải pháp dựa trên thảo luận của tôi ở đây:

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

Vấn đề này có thể được thực hiện trong o (fib (n + 2)) với một thuật toán DP chuẩn. Chúng tôi có chính xác n vấn đề phụ và nút lên chúng tôi có thể giải quyết từng vấn đề với kích thước i trong o (fib (i)) thời gian. Tổng hợp chuỗi cung cấp cho fib (n + 2).

Nếu bạn xem xét cẩn thận câu hỏi, bạn thấy rằng đó là chuỗi Fibonacci. Tôi lấy mã Fibonacci chuẩn và chỉ thay đổi nó để phù hợp với điều kiện của chúng tôi.

Không gian rõ ràng là ràng buộc với kích thước của tất cả các giải pháp o (fib (n)).

xem xét mã giả này:

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