Java O(n) O(1)space solution


  • 1
    C
    public class Solution {
        public int numDecodings(String s) {
            if(s.length()==0)return 0;
            if(s.charAt(0)=='0')return 0;
            if(s.length()==1)return 1;
            int last=Character.getNumericValue(s.charAt(0));
            int cur =Character.getNumericValue(s.charAt(1));
            int count=1, lastcount=1, lastlastcount=1;
            if(cur==0){
                if(last!=1&&last!=2)return 0;
                lastcount=1;
            }
            else if(last==1||(last==2&&cur<=6))lastcount=2;
            else lastcount=1;
            if(s.length()==2)return lastcount;
            last = cur;
            for(int i=2; i<s.length(); i++){
                cur = Character.getNumericValue(s.charAt(i));
                if(cur==0){
                    if(last!=1&&last!=2)return 0;
                    count=lastlastcount;
                }
                else if(last==1||(last==2&&cur<=6))count=lastcount+lastlastcount;
                else count = lastcount;
                last = cur;
                lastlastcount=lastcount;
                lastcount=count;
            }
            return count;
        }
    }

Log in to reply
 

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