Simple java solution with O(1) space


  • 13
    L
    public int numDecodings(String s) {
        int n1 =1, n2=1, n3=0;
        if(s.length()==0||s.charAt(0)=='0') return 0;
        for(int i=2; i<=s.length(); i++)
        {
            n3=0;
            if(s.charAt(i-1)!='0') n3=n2;
            int num = Integer.parseInt(s.substring(i-2,i));
            if(num>=10 && num<=26) n3+=n1;
            n1=n2;
            n2=n3;
        }
        return n2;
    }

  • 0
    Y

    hi lmx707, could you explain it? esp. what is the meaning of n1, n2 and n3?


  • 1
    Y

    looks like fibonacci, but i am not sure how it relates to fibonacci...


  • 0
    M

    @yanggao
    If all of two adjacent digits in input are valid for a letter, it will be same as Fibonacci problem.
    Example: input is "11111". Result is equal to "1111" plus "111".

    Here is my Java code with comments. It may help you to understand it:

    public int numDecodings(String s) {
      if (s == null || s.length() == 0 || s.startsWith("0") || s.matches(".*[^12]0.*"))
        return 0;
      int previousResult = 1;
      int result = 1;
      for (int i = 1; i < s.length(); i++) {
        int newResult;
        if (s.charAt(i) == '0') {
          // the last two digits must be converted together
          newResult = previousResult;
        } else if (s.charAt(i - 1) != '0' && Integer.parseInt(s.substring(i - 1, i + 1)) <= 26) {
          // the last two digits may or may not be converted together
          newResult = previousResult + result;
        } else {
          // the last two digits cannot be converted together
          newResult = result;
        }
        previousResult = result;
        result = newResult;
      }
      return result;
    }
    

Log in to reply
 

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