LeetCode : 91. Decode Ways

[congr]

https://leetcode.com/problems/decode-ways/

[congr]

162 same question

test cases "01" => 0 "17" => 2 "27" => 1

[congr]

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty()) return 0;
        return decode(s.toCharArray(), 0);
    }

    int decode(char[] ch, int p) {
        if (p >= ch.length) return 1;
        if (ch[p] == '0') return 0; // "01" no need to go further

        int cnt = 0;
        if ('1' <= ch[p] && ch[p] <= '9') {
            cnt += decode(ch, p+1);
        }

        if (p+1 < ch.length) {
            int second = (ch[p] - '0') * 10 + ch[p+1] - '0'; 
            if (0 < second && second <= 26) cnt += decode(ch, p+2);
        }

        return cnt;
    }
}

[congr]

Memoization

Memoization makes it faster, but recursion itself is slower than iteration.

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty()) return 0;
        int[] d = new int[s.length()];
        return decode(s.toCharArray(), 0, d);
    }

    int decode(char[] ch, int p, int[] d) {
        if (p >= ch.length) return 1;
        if (ch[p] == '0') return 0; // "01" no need to go further
        if (d[p] > 0) return d[p];

        int cnt = 0;
        if ('1' <= ch[p] && ch[p] <= '9') {
            cnt += decode(ch, p+1, d);
        }

        if (p+1 < ch.length) {
            int second = (ch[p] - '0') * 10 + ch[p+1] - '0'; 
            if (0 < second && second <= 26) cnt += decode(ch, p+2, d);
        }

        d[p] = cnt;
        return d[p];
    }
}

[congr]

Check this DP solution

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] memo = new int[n+1];
        memo[n]  = 1;
        memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;

        for (int i = n - 2; i >= 0; i--)
            if (s.charAt(i) == '0') continue;
            else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];

        return memo[0];
    }
}