46. Translate numbers into strings

“This is the 21st day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Force button topic link

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”

Tip:

0 <= num < 2^31

Ideas:

This problem can be solved using dynamic programming. First, we need to find the dynamic programming equation:

First of all definedp[i]saidiBit digital solutions.
If the firstiDigit and digiti - 1Bits of numbers can be combined and translated into strings. So,dp[i] = dp[i - 1] + dp[i - 2]. The reason is that the last two digits can be combined or translated separately. In other words, when you unpack it, it’sdp[i - 1]The number of; When it comes time to merge, it isdp[i - 2]So the sum of the two is equal todp[i]
If the firstiDigit and digiti - 1Digits cannot be combined. So,dp[i] = dp[i - 1].
Finally, you need to find the initial values for the dynamic programming. Available:dp[0] = dp[1] = 1. In other words,0A digital and1There’s only one way to translate a number.

Having found the dynamic programming equation, we now need to think about how to write the code. Code first:

Dynamic programming

/ * * *@param {number} num
 * @return {number}* /
var translateNum = function(num) {
    let s = String(num);
    let a = 1;
    let b = 1;
    for (let i = 2; i <= s.length; i++) {
        let temp = s.slice(i - 2, i);
        let c = (temp >= '10') && (temp <= '25')? a + b : a; b = a; a = c; }return a;
};
Copy the code

Time complexity O(n).
Space complexity O(n).

Analysis:

To facilitate traversal, the number is first converted to a string for processing. Initialize the values of dp[0] and dp[1], both of which are 1.

Then loop through the string. Notice the loop condition here, because we need to cut two bits of the string to see if they can be combined. Since the Slice method is a left-closed and right-open interval, we traverse from the third bit, at index 2. And the termination condition is I ≤ S. length, again because it’s closed on the left and open on the right.

The truncated string is then used for comparison. If two characters can be combined or separated. Dp [I] = dp[i-1] + dp[i-2], so c = a + b. If dp[I] = dp[i-1] cannot be combined, c = a is executed.

Since dp[I] is only associated with the first two numbers, this is saved by maintaining additional variables. By alternating variables, the final result is the value of variable A, which can be returned.

In terms of complexity, time complexity is the number of traversal times of the string. Space complexity is the extra space required to convert to strings.

conclusion

Think of it as a special step-hopping problem, where each step has a number on it. The particularity lies in the fact that it is optional to jump one step or two steps. To jump two steps in this problem, one condition must be met, that is, only when the decimal number of the digits on the two steps to jump is between 10 and 25 can we jump.

46. Translate numbers into strings