DP Solution with O(1) space, O(n) time


  • 0
    I

    In the DP solution, we need not keep in memory the no. of ways to decode the string at every digit, just the number of ways to decode the next 2 digits.

    DP Solution:
    f(i) = No of ways to decode the string starting at index i

    If s[i] == 0, f(i) = 0, else:
    f(i) = f(i+1) + f(i+2) if s.substring(i, i+2) <= 26
    f(i) = f(i+1) s.substring(i, i+2) > 26

    Code:

    public class Solution {
    	public int numDecodings(String s) {
    	      
            if(s.equals("")) {
                return 0;
            }
            int curr = 0;
            int next2 = 1;
            int next1 = s.charAt(s.length() - 1) == '0'? 0:1;
            if(s.length() == 1) {
                return next1;
            }
            
            int i = s.length() - 2;
            
            while(i >= 0) {
                if(s.charAt(i) == '0') {
                    curr = 0;
                } else {
                    if(Integer.valueOf(s.substring(i,i+2)) <= 26) {
                        curr = next1 + next2;
                    } else {
                        curr = next1;
                    }
                }
                i--;
                next2 = next1;
                next1 = curr;
            }
            return curr;   
        }
    }
    

Log in to reply
 

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