Solving by mathematical forumla (Fibonacci sequence)


  • 0
    R

    UPDATE...I found an even better method. Details are after the first code block below.

    It seems everyone else has taken the approach of processing the string character by character, counting up the number of possible combinations at each character. I took a different approach, and solved it by mathematical formula.

    The way I process the string is essentially by breaking it into blocks of consecutive 1s and 2s (since those are the only digits which can give you you multiple possible decodings). In each block of 1s and 2s, I count the number of digits, and then mathematically calculate the number of possible combinations within those blocks.

    For each block, I add up all the possible arrangements: no pairs of numbers (ie: all single digits), 1 pair of numbers, 2 pairs, 3 pairs, etc.The trick for this was to come up mathematical formulas for each of possible combinations

    no pairs: only 1 possible way

    1 pair: as long as n >=2, you have (n-1) possible ways

    2 pair: as long as n >= 4, you have (n-3)(n-2)/2 possible ways

    3 pair: as long as n >= 6, you have (n-5)(n-4)(n-3)/(23) possible ways

    4 pair: as long as n >= 8, you have (n-7)(n-6)(n-5)(n-4)/(2
    34) possible ways

    5 pair: as long as n >= 10, you have (n-9)(n-8)(n-7)(n-6)(n-5)/(2
    345) possible ways

    etc...

    One nice thing about this solution is that, once you've calculated the number of possibilities for a string of n 1s and 2s, you can cache that value in a hashmap and never have to calculate it again, so it would be great for really long strings

    public class Solution {
    
    private static HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>(); 
    
    private int calc_combinations(int n)
    {
    	//rather than recalculate this every time, cache values which we've already calculated
    	Integer cached = cache.get(n);
    	if (cached != null) return cached;
    	
    	int result = 1;
    	int denominator = 1;
    	for(int i=1; i <= n/2; i++)
    	{
    		denominator *= i;
    		
    		int val = 1;
    		for(int j=i; j < 2*i; j++)
    			val *= (n-j);
    		result += val/denominator;
    	}
    	cache.put(n, result);
    	return result;
    }
    
    public int numDecodings(String s) {
    	if (s.length() == 0) return 0;
    	
    	char[] c = s.toCharArray();
        int len = c.length;
        
        int result = 1;
    
        int i = -1;
        while(++i < len)
        {
        	if (c[i] == '0') return 0; //invalid...can't have a zero here
        	if (c[i] > '2') continue; //if this is greater than 2, then there's only 1 way it can be decoded
    
        	//now we found we have a 1 or a 2...lets see how many we find in a row
        	int start = i;
        	while((++i < len) && ((c[i] == '1')||(c[i] == '2')));
        	int count = i - start;
    
        	//now, depending on what our next digit (if any) is, we can calculate how many combination are possible
        	//if there is no next char, or the next char would give us a 27 or greater, then only worry about the combinations within the 1s and 2s
        	if ((i == len) || ((c[i] >= '7') && (c[i-1] == '2')))  
        		result *= calc_combinations(count);
        	//otherwise, if the char is anything but a zero, then we add the number of combination without the next char, and the number including it
        	else if (c[i] != '0')
        		result *= calc_combinations(count) + calc_combinations(count-1);
        	//our next char is a zero...we know our last 1 or 2 MUST go with it, so calculate only the combinations of the other 1s and 2s
        	else
        		result *= calc_combinations(count-1);
        }
        
        return result;
    }
    

    }

    UPDATE:
    I actually started looking at this further, thinking it had some more optimization left. Stupidly, I was so entrenched in the algorithm of how you calculate the number of combinations of various length strings of 1s and 2s that I never bothered to even look at what the final value for each of those lengths are. It turns out, they are they Fibonacci sequence (interesting...I personally have never had a practical application for that until now).

    Knowing that, I was able to optimize this quite a bit. It turns out that for a 32-bit signed integer, there are only 46 values before the integer overflows. So, I precalculate the entire sequence ahead of time. For a further TINY TINY optimization, you could even calculate the values by hand and embed them all right in the code, but that takes less than 1 ms to do, so I didn't bother

    public class Solution {
    	private static int[] combinations = new int[46]; //note: after 46, the value overflows
    
    	static
    	{
    		combinations[0] = 1;
    		combinations[1] = 1;
    		for (int i = 2; i < combinations.length; i++)
    			combinations[i] = combinations[i-1] + combinations[i-2];
    	}
    	
    	protected int numDecodings(String s) {
    		if (s.length() == 0) return 0;
    		
    		char[] c = s.toCharArray();
    	    int len = c.length;
    	    
    	    int result  = 1;
    	    int i = -1;
    	    while(++i < len)
    	    {
    	    	if (c[i] == '0') return 0; //invalid...can't have a zero here
    	    	if (c[i] > '2') continue; //if this is greater than 2, then there's only 1 way it can be decoded
    
    	    	//now we found we have a 1 or a 2...lets see how many we find in a row
    	    	int start = i;
    	    	while((++i < len) && ((c[i] == '1')||(c[i] == '2')));
    	    	int count = i - start;
    
    	    	//now, depending on what our next digit (if any) is, we can calculate how many combinations are possible
    
    	    	//if there is no next char, or the next char would give us a 27 or greater, 
    	    	//then only worry about the combinations within the 1s and 2s
    	    	if ((i == len) || ((c[i] >= '7') && (c[i-1] == '2')))  
    	    		result *= combinations[count];
    
    	    	//if our next char is a zero...we know our last 1 or 2 MUST go with it, 
    	    	//so calculate only the combinations of the other 1s and 2s
    	    	else if (c[i] == '0')
    	    		result *= combinations[count-1];
    
    	    	//otherwise,  we add the number of combination without the next char + the number including it
    	    	//note the shortcut...we can use count+1 instead of count and count-1
    	    	else
    	    		result *= combinations[count+1];
    	    }
    	    
    	    return result;
    	}
    

    }

    This seems to be the fastest solution so far (I've benchmarked it against several of the other solutions posted). Not sure how much more optimization can be done, as this method has a minimal number of mathematical operations and array accesses.

    I tried doing an alternative optimization...counting how many times each length sequence occurs, then doing the all of the calculations at the end. This has the advantage that you can do way less multiplications. If you've got 64 occurences of a particular sequence, instead of doing 64 multiplications, you can do squaring-by-exponentiation and get the same result with 6 to 12 multiplcation plus a some bit shifts/conditional jumps. However, this only seems to give a small boost, and only when processing HUGE strings (it can be considerably worse with smaller strings). And by the time you get that far, your calculation has probably overflowed a 32-bit int, so you'd probably have to convert to long.

    Example:

    	int[] counts = new int[combinations.length];
    int i = -1;
    int max_index = -1;
    while(++i < len)
    {
    	.....omitted....
    
    	int index;
    	if ((i == len) || ((c[i] >= '7') && (c[i-1] == '2')))
    		index = count;
    	else if (c[i] == '0')
    		index = count-1;
    	else
    		index = count+1;
    
    	counts[index]++;
    	if (index > max_index) max_index = index;
    }
    
    int result  = 1;
    for(i = 2; i <= max_index; i++)
    {
    	int exponent = counts[i];
    	if (exponent == 0) continue;
    	int base = combinations[i];
    	while (exponent > 1)
    	{
    		if ((exponent & 1) == 1)
    			result *= base;
    		exponent >>= 1;
    		base *= base;
    	}
    }
    
    return result;

  • 1
    L

    I have the same idea, but I don't calculate Fibonacci, it's O(n) with O(1) space, below is my code:

    public class Solution
    {
        public int numDecodings(String s)
        {
            if (s.length() == 0)
            {
                return 0;
            }
            else
            {
                int prev2 = 1;
                int prev1 = s.charAt(0) != '0' ? 1 : 0;
                int num = prev1;
                for (int i = 1; i < s.length(); ++i)
                {
                    num = 0;
                    if (s.charAt(i) != '0')
                    {
                        num += prev1;
                    }
                    
                    if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6'))
                    {
                        num += prev2;
                    }
                    
                    prev2 = prev1;
                    prev1 = num;
                }
                
                return num;
            }
        }
    }

  • 0
    J

    Great. It reminds me of a math problem about walking down steps and you can just go one or two steps down every time. So I modified your code to describe this idea (C++):

    class Solution {
    public:
        int numDecodings(string s) {
            if (s.empty() || s[0] == '0') return 0;
            // Fibonacci rocks!
            int a = 1;
            int b = 1;
            for (int i = 1; i < s.length(); i++) {
                int n = 0;
                if (s[i] != '0') n += b;  // from the previous step
                if (s[i-1] == '1' || (s[i-1] == '2' && s[i] <= '6')) {
                    n += a;  // from the step before the previous step
                }
                a = b;
                b = n;
                //if (a == 0 && b == 0) break;
            }
            return b;
        }
    };
    

  • 0
    B

    I am interested in how you calculate "the possible arrangements for m pairs in n digits (n>=2m). this got me for an hour.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.