Skip to content

Files

Latest commit

e3780b7 · Jul 19, 2024

History

History

0091.Decode Ways

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Jul 19, 2024
Jul 15, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
comments difficulty edit_url tags
true
中等
字符串
动态规划

English Version

题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码

"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'

然而,在 解码 已编码的消息时,你意识到有许多不同的方式来解码,因为有些编码被包含在其它编码当中("2""5""25")。

例如,"11106" 可以映射为:

  • "AAJF" ,将消息分组为 (1, 1, 10, 6)
  • "KJF" ,将消息分组为 (11, 10, 6)
  • 消息不能分组为  (1, 11, 06) ,因为 "06" 不是一个合法编码(只有 "6" 是合法的)。

注意,可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串,返回 0

题目数据保证答案肯定是一个 32 位 的整数。

 

示例 1:

输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3:

输入:s = "06"
输出:0
解释:"06" 无法映射到 "F" ,因为存在前导零("6" 和 "06" 并不等价)。

 

提示:

  • 1 <= s.length <= 100
  • s 只包含数字,并且可能包含前导零。

解法

方法一:动态规划

我们定义 f [ i ] 表示字符串的前 i 个字符的解码方法数,初始时 f [ 0 ] = 1 ,其余 f [ i ] = 0

考虑 f [ i ] 如何进行状态转移。

  • 如果第 i 个字符(即 s [ i 1 ] )单独形成编码,那么它对应一种解码方式,即 f [ i ] = f [ i 1 ] 。前提是 s [ i 1 ] 0
  • 如果第 i 1 个字符和第 i 个字符组成的字符串在 [ 1 , 26 ] 范围内,那么它们可以作为一个整体,对应一种解码方式,即 f [ i ] = f [ i ] + f [ i 2 ] 。前提是 s [ i 2 ] 0 ,且 s [ i 2 ] s [ i 1 ] [ 1 , 26 ] 范围内。

时间复杂度 O ( n ) ,空间复杂度 O ( n ) 。其中 n 是字符串的长度。

Python3

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        f = [1] + [0] * n
        for i, c in enumerate(s, 1):
            if c != "0":
                f[i] = f[i - 1]
            if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:
                f[i] += f[i - 2]
        return f[n]

Java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] = f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && Integer.valueOf(s.substring(i - 2, i)) <= 26) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

C++

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int f[n + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0') {
                f[i] = f[i - 1];
            }
            if (i > 1 && (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6')) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

Go

func numDecodings(s string) int {
	n := len(s)
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; i <= n; i++ {
		if s[i-1] != '0' {
			f[i] = f[i-1]
		}
		if i > 1 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) {
			f[i] += f[i-2]
		}
	}
	return f[n]
}

TypeScript

function numDecodings(s: string): number {
    const n = s.length;
    const f: number[] = new Array(n + 1).fill(0);
    f[0] = 1;
    for (let i = 1; i <= n; ++i) {
        if (s[i - 1] !== '0') {
            f[i] = f[i - 1];
        }
        if (i > 1 && (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6'))) {
            f[i] += f[i - 2];
        }
    }
    return f[n];
}

C#

public class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0') {
                f[i] = f[i - 1];
            }
            if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

我们注意到,状态 f [ i ] 仅与状态 f [ i 1 ] 和状态 f [ i 2 ] 有关,而与其他状态无关,因此我们可以使用两个变量代替这两个状态,使得原来的空间复杂度 O ( n ) 降低至 O ( 1 )

Python3

class Solution:
    def numDecodings(self, s: str) -> int:
        f, g = 0, 1
        for i, c in enumerate(s, 1):
            h = g if c != "0" else 0
            if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:
                h += f
            f, g = g, h
        return g

Java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int f = 0, g = 1;
        for (int i = 1; i <= n; ++i) {
            int h = s.charAt(i - 1) != '0' ? g : 0;
            if (i > 1 && s.charAt(i - 2) != '0' && Integer.valueOf(s.substring(i - 2, i)) <= 26) {
                h += f;
            }
            f = g;
            g = h;
        }
        return g;
    }
}

C++

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int f = 0, g = 1;
        for (int i = 1; i <= n; ++i) {
            int h = s[i - 1] != '0' ? g : 0;
            if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
                h += f;
            }
            f = g;
            g = h;
        }
        return g;
    }
};

Go

func numDecodings(s string) int {
	n := len(s)
	f, g := 0, 1
	for i := 1; i <= n; i++ {
		h := 0
		if s[i-1] != '0' {
			h = g
		}
		if i > 1 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) {
			h += f
		}
		f, g = g, h
	}
	return g
}

TypeScript

function numDecodings(s: string): number {
    const n = s.length;
    let [f, g] = [0, 1];
    for (let i = 1; i <= n; ++i) {
        let h = s[i - 1] !== '0' ? g : 0;
        if (i > 1 && (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6'))) {
            h += f;
        }
        [f, g] = [g, h];
    }
    return g;
}

C#

public class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        int f = 0, g = 1;
        for (int i = 1; i <= n; ++i) {
            int h = s[i - 1] != '0' ? g : 0;
            if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
                h += f;
            }
            f = g;
            g = h;
        }
        return g;
    }
}