Given the string, find the number of possible codes the string can generate using Python

You can make the following points:

• There may be invalid sequences: 0 must always precede either 1 or 2. If there is a violation of this rule, 0 must be returned (or a raised exception)
• All minimum subsequences in the input that can increase the number of combinations start with 1 or 2. So, for example, a line that starts with 7 will produce as many combinations as the same input as 7 deleted.
• Subsequential sequences that allow multiple combinations can be isolated from each other, since they also end in can never be matched with the next character being in the input.

• Let the definition of "matching subsequence" be: any subsequence that returns 2 or more (number of combinations) if treated as a separate input, and that returns a smaller value if one character is made shorter (remove one character from either end) and not return a larger value if you make 1 character longer on each side of the subsequence (i.e. not on any character, but as a subsequence in the input, of course). The regex matching such matching subsequences is

  [12]*?(?:[3-6]|1[3-9]|(?=.0|$))
  
        
  
          
          
          
        
  
      

• The number of combinations represented by one matching subsequence is determined by the following recursive form (where n
  
  is the length of the subsequence):

  C(n) = 1 when n == 1
       = 2 when n == 2
       = C(n-1) + c(n-2) when n > 2
  
        
  
          
          
          
        
  
      

  This is a Fibonacci series (shifted by one index position as true Fibonacci has Fib(2) = 1
  
  , but this is just a detail).

• So, if we first find the longest matching subsequence, we would know how many Fibonacci numbers will generate (and no more!), And we only have to do this generation once. Then we can simply take the product of the Fibonacci numbers corresponding to the lengths of the subsequences.

Here is the commented code that implements these ideas:

import re
from operator import mul
from functools import reduce # For Python 3.x

def get_combination(string):
    def fib_to(n):
        fibs = [1, 1] # Real Fibonacci would need [0, 1], but we want fib[2] to be 2.
        for i in range(2, n+1):
            fibs.append(fibs[-1] + fibs[-2])
        return fibs

    # Detect an invalid sequence, where a 0 occurs without a 1 or 2 preceding it  
    if re.search(r"(?<![12])0", string):
        return 0
    # Find all sub sequences where a variation is possible
    sequences = re.findall(r"[12]*?(?:[3-6]|1[3-9]|(?=.0|$))", string)
    if not sequences:
        return 1
    # Get the sizes of all these sequences; it is all we need to know
    sizes = [len(seq) for seq in sequences]
    # Generate Fibonacci numbers up to the maximum needed:
    fib = fib_to(max(sizes))
    # Take the product of the sizes for each of the sequences
    return reduce(mul, [fib[size] for size in sizes], 1)

tests = [ # inputs combined with expected outputs
    ["", 1],
    ["2", 1],
    ["12", 2],
    ["121", 3],
    ["1234", 3],
    ["2121", 5],
    ["210", 1],
    ["210210", 1],
    ["22102210", 4],
    ["219219", 9],
    ["07", 0],
    ["507", 0]
]

for test in tests:
    res = get_combination(test[0])
    if res != test[1]: 
        print("Error - Input: '{}' Output: {} Expected: {}".format(test[0], res, test[1]))
    else:
        print("OK - Input: '{}' Output: {}".format(test[0], res))

      

        
        
        
      

    

See how it works on repl.it

Pay attention to the checked edge cases. Your code fails several of these tests.

At the time of writing, none of the answers give the correct result for entering "07" (which should return 0), and kashif's answer is the only one that only fails in this test.

Here is the test result for each of the answers at the time of writing: repl.it