常梦网 常梦网

Decode Ways leetcode - Ryan的修炼之路

时间: 2024-04-18  热度:

Decode Ways

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.

动态规划

说明

复杂度

时间复杂度O(n), 空间O(n)

代码

public int numDecodings(String s) {    if (s == null || s.length() == 0) {        return 0;    }    int[] dp = new int[s.length() + 1];    dp[0] = 1;    dp[1] = isValid(s.substring(0, 1))? 1 : 0;    for (int i = 2; i <= s.length(); i++) {        if (isValid(s.substring(i - 1, i))) {dp[i] += dp[i - 1];        }        if (isValid(s.substring(i - 2, i))) {dp[i] += dp[i - 2];        }    }    return dp[s.length()];}public boolean isValid(String s) {    if (s == null || s.length() == 0) {        return false;    }    if (s.charAt(0) == '0') {        return false;    }    int tem = Integer.parseInt(s);//把string变为int    return tem >= 1 && tem <= 26;}

复杂度

时间复杂度O(n), 空间O(1)

说明

因为每次计算i只用到i之前的两个数
所以这里可以只用一个容量为3的数组, 每次i存在[i%3]对应的位置

代码

public int numDecodings(String s) {    if (s == null || s.length() == 0) {        return 0;    }    int[] dp = new int[3];    dp[0] = 1;    dp[1] = isValid(s.substring(0, 1))? 1 : 0;    for (int i = 2; i <= s.length(); i++) {        dp[i % 3] = 0;        if (isValid(s.substring(i - 1, i))) {dp[i % 3] += dp[(i - 1) % 3];        }        if (isValid(s.substring(i - 2, i))) {dp[i % 3] += dp[(i - 2) % 3];        }    }    return dp[s.length() % 3];}public boolean isValid(String s) {    if (s == null || s.length() == 0) {        return false;    }    if (s.charAt(0) == '0') {        return false;    }    int tem = Integer.parseInt(s);//把string变为int    return tem >= 1 && tem <= 26;}

相关阅读