Jamzen的技术博客
0%

LeetCode.解码方法

发表于 分类于 Valine：

一条包含字母A-Z的消息通过以下方式进行了编码：’A’ -> 1，’B’ -> 2，…，’Z’ -> 26; 给定一个只包含数字的非空字符串，请计算解码方法的总数。题目数据保证答案肯定是一个32位的整数。

  1. 示例 1：输入s = “12”, 输出 2
    解释：它可以解码为 “AB”（1 2）或者 “L”（12）。
  2. 示例 2：输入s = “226”, 输出 3
    解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
  3. 示例 3：输入s = “0”, 输出 0
  4. 示例 4：输入s = “1”, 输出 1

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
object NumDecodings {
     def main(args: Array[String]): Unit = {
          //0 -> 1, 1 -> 1 + 1, 2 -> 2 + 1
          println(numDecodings("0"))
          println(numDecodings("1"))
          println(numDecodings("2"))
          println(numDecodings("12"))
          println(numDecodings("226"))
          println(numDecodings("1234"))
          println(numDecodings("2101"))
          println(numDecodings("10011"))
          println(numDecodings("230"))
          println(numDecodings("301"))
     }

     def numDecodings(s: String): Int = {
          //pass "0"
          if (s == null || s == "" || s.charAt(0) == '0') return 0
          //pass -> "1"
          if (s.length == 1 && s.charAt(0) != 0) return 1

          val dp = new Array[Int](s.length)
          dp(0) = 1

          //pass -> "301"
          if (s.substring(0, 2).toInt > 26 && s.charAt(1) == '0') return 0
          if (s.substring(0, 2).toInt <= 26 && s.charAt(1) != '0') dp(1) = 2 else dp(1) = 1

          for (i <- 2 until s.length) {
               if (s.substring(i - 1, i + 1).toInt <= 26) {
                    if (s.charAt(i) == '0') {
                         //pass "12001"
                         if (s.charAt(i - 1) == '0') return 0
                         dp(i) = dp(i - 2)
                    } else {
                         if (s.charAt(i - 1) == '0') dp(i) = dp(i - 1) else dp(i) = dp(i - 2) + dp(i - 1)
                    }
               } else {
                    //pass -> "230"
                    if (s.charAt(i) == '0') return 0
                    dp(i) = dp(i - 1)
               }
          }
          dp(s.length - 1)
     }
}