题目连接

解码方法

题目描述

image.png

实现代码

  1. class Solution {
  2.     public int numDecodings(String s) {
  3.         int n = s.length();
  4.         int[] f = new int[n + 1];
  5.         f[0] = 1;
  6.         for (int i = 1; i <= n; ++i) {
  7.             if (s.charAt(i - 1) != '0') {
  8.                 f[i] += f[i - 1];
  9.             }
  10.             if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
  11.                 f[i] += f[i - 2];
  12.             }
  13.         }
  14.         return f[n];
  15.     }
  16. }

空间复杂度优化：

  1. class Solution {
  2.     public int numDecodings(String s) {
  3.         int n = s.length();
  4.         // a = f[i-2], b = f[i-1], c=f[i]
  5.         int a = 0, b = 1, c = 0;
  6.         for (int i = 1; i <= n; ++i) {
  7.             c = 0;
  8.             if (s.charAt(i - 1) != '0') {
  9.                 c += b;
  10.             }
  11.             if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
  12.                 c += a;
  13.             }
  14.             a = b;
  15.             b = c;
  16.         }
  17.         return c;
  18.     }
  19. }