8 lines java solution, similar as climbing stair / fibonacci


  • 4
    S

    space: O(1), time: O(N)

    public class Solution {
        public int numDecodings(String s) {
            if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
            int dp0 = 1, dp1 = 1, dp2 = 1;
            for(int i=1; i<s.length(); i++) {
                dp2 = (s.charAt(i)-'0' >=1 && s.charAt(i)-'0' <= 9) ? dp1 : 0;
                dp2 = ( (s.charAt(i-1)-'0' == 1 && s.charAt(i)-'0' >=0 && s.charAt(i)-'0' <=9) ||
                        (s.charAt(i-1)-'0' == 2 && s.charAt(i)-'0' >=0 && s.charAt(i)-'0' <=6) ) ? dp2+dp0 : dp2;
                dp0 = dp1;
                dp1 = dp2;
            }
            return dp2;
        }
    }

  • 0

    Very impressive can you explain your logic a bit. Can you explain the purpose of your different int variables dp(x)


Log in to reply
 

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