Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

Leetcode interview preparation: Decode Ways

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.

Share To

Network Security

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report