“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

1, the title

Given a number, we translate it as a string as follows: 0 to “a”, 1 to “b”… 11 translated as “L”… 25 translates as “Z”. A number can have multiple translations. Program to implement a function that calculates how many different ways a number can be translated.

Example 1:

Input: 12258 Output: 5 Explanation: 12258 has 5 different translations, which are "bCCFI "," bwFI ", "BCZI "," MCFI "and "mzi"Copy the code

Tip:

  • 0 <= num < 2^31

2, train of thought

(Dynamic programming)O(logn)O(logn) O(logn)

Given a number num, translate it into a string according to the rules given in the question, asking how many different ways a number can be translated.

Sample:

Num = 12258, num = 12258, num = 12258

  • 1. Translate each one individually, so that it can be translated into"bccfi".
  • 2. Combine the two adjacent digits together to translate (the combined digits range in10 ~ 25Between)"bwfi"."bczi"."MCFI" and "mzi." ".

The two cases are or and do not affect each other. If you add them together, there will be five different translation ways for 12258. In order to easily combine the two adjacent digits of a number, we can first convert num into a string array s[].

Status means:

We define f[I] to represent how many different ways the first I number can be translated. Then, f[n] represents the number of different translation methods for the first n numbers, which is the answer.

State calculation:

Assuming the string array is S [], for the i-th number, there are two decisions:

  • 1. Separate translations[i]. And since we’re dealing with the number of solutions, if we determine the number of solutionsiThe translation of a number, then before translationiA number and translation beforei - 1The number of methods are the same, namelyf[i] = f[i - 1]. (s[]Array subscript from1Start)

  • 2. Combine s[I] and S [i-1] to translate (the combined number ranges from 10 to 25). If the translation method of the i-th and i-1 number is determined, the number of translation methods for the i-th number before translation and i-2 number before translation are the same, that is, F [I] = F [i-2]. (s[] array index starts at 1)

Finally, the number of schemes of the two decisions is added up, so the state transition equation is: F [I] = F [i-1] + F [i-2].

Initialization:

F [0] = 1, the number of methods to translate the first 0 numbers is 1.

Why is the number of schemes without a single number1?

F [0] represents the number of methods to translate the first 0 digits. Such state definition is actually meaningless, but the value of F [0] needs to ensure that the boundary is correct, that is, f[1] and F [2] are correct. For example, there is only one way to translate the first number, namely, f[1] = f[1-1] = 1. If the first two numbers can be translated together, then f[2] = f[1] + f[0] = 2, otherwise, the second number can only be translated separately, that is, F [2] = f[1] = 1. Therefore, in any case f[0] taking 1 guarantees that f[1] and f[2] are correct, so f[0] should take 1.

Implementation details:

In the derivation of the state transition equation, the subscript of the assumed array S [] starts from 1, while the subscript of the actual array S [] starts from 0. In order to match the values of the combined digits, the values of S [i-1] and S [I] should be moved forward by one digit. Take s and s [I – 1] [2] I -, namely composite value t = (s/I – 2 – ‘0’) * 10 + s] [I – 1 – ‘0’.

When deriving the state transition equation, the default array subscript usually starts at 1, so the state representation can correspond to the actual array, so it’s easier to understand, but you have to misplace it in the actual calculation, so I want you to pay attention to that.

Time complexity analysis: O(logn)O(logn)O(logn), the number of nums bits, that is, logn, base 10.

Space complexity analysis: O(n)O(n)O(n).

C++ code

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num); // Convert a number to a string
        int n = s.size();
        vector<int> f(n + 1);
        f[0] = 1;      / / initialization
        for(int i = 1; i <= n; i++){
            f[i] = f[i - 1]; [I] [I]
            if(i > 1) {int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
                if(t >= 10 && t <= 25)    // The combined number ranges from 10 to 25
                    f[i] += f[i - 2];     // Combine s[I] with s[i-1]}}returnf[n]; }};Copy the code

4. Java code

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num); // Convert a number to a string
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;  / / initialization
        for(int i = 1; i <= n; i++){
            f[i] = f[i - 1];  [I] [I]
            if(i > 1) {int t = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                if(t >= 10 && t <= 25) // The combined number ranges from 10 to 25
                    f[i] += f[i - 2];  // Combine s[I] with s[i-1]}}returnf[n]; }}Copy the code