In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-04-02 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Network Security >
Share
Shulou(Shulou.com)06/01 Report--
1 topic
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1'B' -> 2... 'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
public int numDecodings(String s);
2 thoughts
One-dimensional dynamic programming, lazy, copy the blog post.
Analysis: It should be noted that if there is a 0 in the sequence that cannot be matched, then the decoding method is 0, such as the sequence 012, 100 (the second 0 can be combined with 1 to form 10, and the third 0 cannot match).
Recursive solutions are easy, but large collections can time out. Converting to dynamic programming, assume dp[i] denotes the sequence s[0... i-1]
The dynamic programming equation is as follows:
Initial conditions: dp[0] = 1, dp[1] = (s[0] == '0')? 0 : 1
dp[i] = ( s[i-1] == 0 ? 0 : dp[i-1] ) + ( s[i-2,i-1] can represent letters? dp[i-2] : 0 ), where the first component is to put s[0... Consider the last digit of i-1 as a letter, and the second component is s[0... Consider the last two digits of i-1 as a single letter
Complexity: O(n); Space O(n)
3 code public int numDecodings(String s) { // 1. Initialize final int len = s.length(); if (len == 0) return 0; int[] dp = new int[len + 1]; dp[0] = 1; if (s.charAt(0) != '0') dp[1] = 1; else dp[1] = 0; // 2. One-dimensional DP equation for (int i = 2; i
Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.
Views: 0
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.