Leetcode - Algorithm - Decode Ways

  2017-05-01 21:45:49 +0000   |     algorithm leetcode dynamic programming string   |   Viewed times   |    

题目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message 12, it could be decoded as AB (1 2) or L (12).

The number of ways decoding 12 is 2.

暴力递归

这个问题的关键就是当出现小于等于26的组合的时候，会出现两个分支，考虑12345这种情况，在遇到1的时候，

1 + "2345"子问题
12 + "345"子问题

需要特殊处理0的情况，

1 + "0345"子问题  # "0345"不是正确的编码格式，会解码错误
10 + "345"子问题

暴力递归一定会重复解决很多次相同子问题，但还是写一下，练手。递归的思路是，用一个int[0]做计数器，每次走通到最后，count[0]++。

代码

public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0) { return 0; }
        char[] c = s.toCharArray();
        int[] count = new int[]{ 0 };
        recursive(c,0,count);
        return count[0];
    }
    public void recursive(char[] c, int cur, int[] count) {
        if (cur >= c.length) { count[0]++; return; }
        if (c[cur] == '0') { return; }
        recursive(c,cur+1,count);
        if (cur+1 < c.length && (c[cur] == '1' || (c[cur] == '2' && c[cur+1] <= '6'))) {
            recursive(c,cur+2,count);
        }
    }
}

结果

果然超时。 decode-ways-1

自底向上的动态规划

记录下每个处理过的子问题的结果。这里递归是DFS深度优先的，所以是自底向上的。

代码

public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0) { return 0; }
        char[] c = s.toCharArray();
        Map<Integer,Integer> memo = new HashMap<>();
        memo.put(s.length(),1);
        return recursive(c,0,memo);
    }
    public int recursive(char[] c, int cur, Map<Integer,Integer> memo) {
        Integer res = memo.get(cur);
        if (res != null) { return res; }
        if (c[cur] == '0') {
            memo.put(cur,0);
            return 0;
        }
        res = recursive(c,cur+1,memo);
        if (cur+1 < c.length && (c[cur] == '1' || (c[cur] == '2' && c[cur+1] <= '6'))) {
            res = res + recursive(c,cur+2,memo);
        }
        memo.put(cur,res);
        return res;
    }
}

结果

银弹！ decode-ways-2

简单用int[]替代Map做备忘录

代码

public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0) { return 0; }
        char[] c = s.toCharArray();
        int[] memo = new int[c.length+1];
        Arrays.fill(memo,-1);
        memo[c.length] = 1;
        return dp(c,0,memo);
    }
    public int dp(char[] c, int cur, int[] memo) {
        Integer res = memo[cur];
        if (res != -1) { return res; }
        if (c[cur] == '0') {
            memo[cur] = 0;
            return 0;
        }
        res = dp(c,cur+1,memo);
        if (cur+1 < c.length && (c[cur] == '1' || (c[cur] == '2' && c[cur+1] <= '6'))) {
            res = res + dp(c,cur+2,memo);
        }
        memo[cur] = res;
        return res;
    }
}

结果

简单用int[]替代Map又快了一倍。 decode-ways-3

迭代版动态规划

因为是自底向上的动态规划，就是从后往前填表的一个过程。而且有点类似Fibonacci数列。

代码

public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0) { return 0; }
        char[] c = s.toCharArray();
        int[] memo = new int[c.length+1];
        memo[c.length] = 1;
        for (int i = c.length-1; i >= 0; i--) {
            if (c[i] == '0') { memo[i] = 0; continue; }
            if (i+1 < c.length && (c[i] == '1' || (c[i] == '2' && c[i+1] <= '6'))) {
                memo[i] = memo[i+1] + memo[i+2];
            } else {
                memo[i] = memo[i+1];
            }
        }
        return memo[0];
    }
}

结果

更快了。 decode-ways-4