Wednesday, November 26, 2014

Decode Ways

//dp, from anniekim
int numDecodings(string s) {
    if (s.empty() || s[0] == '0')
        return 0;
    int N = s.size();
    int dp[N+1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 1; i < N; ++i)
    {
        if (s[i] == '0')
        {
            if (s[i-1] != '1' && s[i-1] != '2')
                return 0;
            dp[i+1] = dp[i-1];
        }
        else
        {
            int num = s[i] - '0' + (s[i-1] - '0') * 10;
            if (num >= 11 && num <= 26)
                dp[i+1] = dp[i] + dp[i-1];
            else
                dp[i+1] = dp[i];
        }
    }
    return dp[N];
}

//same idea, but less space
int numDecodings(string s) {
    if (s.empty() || s[0] == '0')
        return 0;
    int N = s.size();
    int cur=0,prev1=1,prev2=1;
    for (int i = 1; i < N; ++i)
    {
        if (s[i] == '0')
        {
            if (s[i-1] != '1' && s[i-1] != '2')
                return 0;
            cur = prev2;
        }
        else
        {
            int num = s[i] - '0' + (s[i-1] - '0') * 10;
            if (num >= 11 && num <= 26)
                cur = prev1 + prev2;
            else
                cur = prev1;
        }
        prev2=prev1;
        prev1=cur;
    }
    return prev1;
}

//another flavor
    int numDecodings(string s) {
        if(!s.size()||s[0]=='0')return 0;
        if(s.length()==1) return 1;
        int cur=0,prev1=1,prev2=1;
        for(int i=1;i<s.length();i++)
        {
            if(s[i]!='0')
                cur+=prev1;
            if((s[i-1]=='1'||s[i-1]=='2'&&s[i]<'7'))
                cur+=prev2;
            prev2=prev1;
            prev1=cur;
            cur=0;
        }
        return prev1;
    }

No comments:

Post a Comment