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?


  • 2
    Y

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


  • 1
    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;
    }
    

  • 0
    S

    @Mark_89 Brief but brilliant explanation for Fibonacci! And the regulation expression wowed me... Thanks!


Log in to reply
 

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