Column website www.jiuzhang.com | | nine chapters algorithm
Topic describes
A message containing A to Z is encrypted as follows: ‘A’ -> 1 ‘B’ -> 2… ‘Z’ – 26
In addition to the above rules, the encrypted string may also contain the character ”, which can be treated as a numeric character between 1 and 9. Given an encrypted message containing numeric characters and “, there are several ways to decode the question. Since the answer may be large, just return the answer modulo 10^9+7.
Sample 1: input: “*” output: 9: the encrypted information can be decoded as the string: “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H” and “I”.
Example 2: Input: “1” Output: 18 Description: “1” can be “11”, “12”,…… “19”, each representation can be decoded as either a single character or as two characters, and the answer is 9+9=18.
Analysis of the problem
This problem is the follow up of decoding method 1. The difference is that a wildcard character * is added, which can be solved by partition type dynamic programming. Because for an encrypted string, the last bit is separated separately, and the decoding scheme number of this bit is independent of the decoding scheme number of the previous remaining strings. Multiply the two to get the total number of schemes in this case, and then consider the last two separate out to decode into a character, using the same method to get the number of schemes, add the two can get the total number of schemes in the original problem.
In the decoding method, consider whether the current bit is decoded as a single character or as a single character together with the previous bit. In this case, the same consideration is taken, but with a little more context.
State representation and initialization: Set the encrypted string as S, the i-th bit of S as S [i-1], f[I] as the number of decoding methods for the first I characters of S, f[0]=1
State transition:
S [i-1] decoded separately into a single character:
S [i-1] is a numeric character: if s[i-1]==’0′, s[i-1] cannot be decoded as a single character, and its contribution to f[I] is 0. If s [I – 1)! =’0′, then S [i-1] can be decoded as a character, and at the same time, there are f[i-1] decoding modes for the pre-i-1 bits, which contributes f[i-1] to f[I].
S [i-1]== “: S [i-1] can be decoded into a character and there are 9 possibilities, for each of which the former i-1 bit has f[i-1] medium decoding, so there are 9f[i-1] medium decoding in this case.
S [i-2] and S [i-1] decode together into a single character:
Both s[i-2] and S [i-1] are numeric characters: if the digits are not between 10 and 26, s[i-2] and S [i-1] cannot be decoded into a character together, contributing 0 to f[I]. Otherwise, s[i-2] and S [i-1] can be decoded together into a single character, contributing f[I] to f[i-2].
If s[i-1]==’*’, s[i-2] is a numeric character: in this case, only “1” and “2” can be decoded into a character, so if s[i-2] is not ‘1’ or ‘2’, then s[i-2] and S [i-1] cannot be decoded into a character together, contributing 0 to the answer; If s[i-2]==’1′, then “1” can be expressed as “11”, “12”… , “19”, decoded as “K” to “S”, a total of 9 possibilities, for each possibility, the former I-2 has f[i-2] decoding mode, contribution of 9F [i-2]; If s[i-2]==’2′, then “2” can be expressed as “21”, “22”, “23”, “24”, “25”, and “26” can be decoded into a character. There are 6 possibilities, and again, its contribution is 6f[i-2].
If s[i-2]==’*’, s[i-1] is a numeric character: Also consider the range of possible digits formed by these two digits (10 to 26). If [] I – 1 s between ‘0’ and ‘6’, s [2] I – can take ‘1’ or ‘2’, two possible contribution to the f [I] for 2 * f [I – 2); If s[i-1] is between ‘7’ and ‘9’, then s[i-1] can only take ‘1’, otherwise it cannot decode two characters together into one character, contributing f[i-2].
If s[i-2] and s[i-1] are both ‘*’ : “*”, since ” can be expressed as 1 to 9, and the range of digits required to decode into a character is 10 to 26, there are 15 ways to decode into a character, namely 11 to 19 and 21 to 26, the contribution of F [I] is 15*f[i-2].
All calculations involved should be modulo 10^9+7, mindful that multiplications may overflow the intermediate result into 32-bit integers, and should be type-cast. The final answer is f[n], where n is the length of the encrypted string. The time complexity of the algorithm is O(n), and the space complexity is O(n).
The reference program
www.jiuzhang.com/solution/de…
From the perspective of the interviewer
This problem is a partition dynamic programming problem. It becomes slightly more complicated after the addition of ‘*’, but the basic idea is still the same. You can carefully analyze all possible situations.
The difficulty of the question lies in the fact that there are many cases during the state transition, and all possible cases need to be covered. The correct solution can be hire.
Lintcode related questions
www.lintcode.com/zh-cn/probl…
Recommended reading:
- Do I need a cover letter to apply online?
- What are the most popular programming languages of 2017?
- Top 10 Reasons to Drop an Offer
- How to negotiate Google Offer? Listen to this Google Recruiter!
- What about the questions you have done in the interview?
- Snapchat surface by | LA headquarters interview experience
- How to learn about an IT company before an interview? Try the official tech blog!
- The 7 most creative resumes in the history of the Internet
- Using Twitter to find a job | how to look for job information
- Facebook +Onsite Onsite Software
Welcome to follow my wechat official account: Ninechapter.
Elite programmer exchange community, regular release of interview questions, interview skills, job information, etc
