Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to find out how many pat in a string". In the operation process of actual cases, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

There are several Pat.

This is a pat question.

analysis

How to find out how many pats there are in a string. Don't think about triple for loops enumerating all cases, that's not a good way. If you have inspiration, you should be able to guess that this should be a dynamic programming problem.

First of all, let's break down the problem briefly. If you ask how many p's are in the original string. Then it is easy to enumerate once. For example, ppp is a sequence of three p.

If you take a, what is the number of pa strings? Pa is composed of p and a. Finding the number of pa must have a lot to do with a, and each a may make up several pa depending on the number of p before this a. Add up pa at all a positions. For example, pppapa can be combined into 3+4=7 pa.

Similarly, it is easy to know how many pats there are. To solve pat, you need to find each t, and then know how many pa are in front of the current position. Superposition solution can obtain the result. It is better to combine the flow chart below.

different sub-sequences

Title Description:

Given a string s and a string t, count the number of occurrences of t in a subsequence of s.

A subsequence of a string is a new string formed by deleting some (or none) characters without disturbing the relative positions of the remaining characters. (For example,"ACE" is a subsequence of "ABCDE" and "AEC" is not)

The question data ensures that the answer fits within the 32-bit signed integer range.

Example 1:

Input: s = "rabbit", t = "rabbit" Output: 3 Explanation: As shown in the figure below, there are three ways to get "rabbit" from s. (The upper arrow symbol ^indicates the selected letter) rabbit ^^^^rabbit ^^^rabbit ^^^^rabbit ^^^rabbit ^^rabbit ^rabbit ^^rabbit ^^rabbit ^rabbit ^rabbit ^

Example 2:

Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown in the figure below, there are 5 ways to get "bag" from s. (The upper arrow ^indicates the selected letter) babgbag ^^ babgbag ^^ ^ babgbag ^ ^^ babgbag ^ ^^ babgbag ^^^

Tip:

0

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.