Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about how C++ can concatenate the substrings of all words. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Substring with Concatenation of All Words concatenates the substrings of all words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring (s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:

S = "barfoothefoobarman"

Words = ["foo", "bar"]

Output: [0,9]

Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.

The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:

S = "wordgoodgoodgoodbestword"

Words = ["word", "good", "best", "word"]

Output: []

This question asks us to concatenate the substrings of all words, that is, given a long string and several words of the same length, it is still a difficult problem to find out the starting position of the substrings concatenating all the words. Suppose there are n words in the words array, and the length of each word is len, so in fact this question allows us to list all the substrings of length nxlen so that it happens to be made up of all the words in the words array. Then it is often necessary to judge whether the substring with the length of len in the s string is a word in words. In order to quickly judge, HashMap can be used. At the same time, because there may be repeated words in the words array, it is necessary to use HashMap to establish the mapping between all words and their occurrence times, that is, to count the number of occurrence of each word.

Traverse all the substrings of length nxlen in s, and when the length of the remaining substrings is less than nxlen, there is no need to judge. So I start from 0 to the end of (int) s.size ()-nxlen. Note that s.size () must be converted to an integer before solving the problem. Be sure to get into the habit of switching to int once you subtract a number after size (), because the return value of size () is unsigned, and once you subtract a number larger than yourself, you will make an error. For each traversal of a substring of length nxlen, you need to verify whether it happens to be composed of all the words in words. The way to check is to take the substring of length len each time to see if it is a word in words. In order to facilitate comparison, set up another HashMap. When the word is not in the words, break it directly, otherwise it will add 1 to its mapping value in the new HashMap, and detect that if the mapping value exceeds the mapping value in the original HashMap, it will also break out, because even if the current word is in the words, it is still inappropriate if the number of times it appears exceeds the number in the words. Outside the for loop, if j is exactly equal to n, it means that the detected n substrings of length len are all words in words and just constitute words, then add the current position I to the result res. For more information, please see the code below:

Solution 1:

Class Solution {public: vector findSubstring (string s, vector& words) {if (s.empty () | | words.empty ()) return {}; vector res; int n = words.size (), len = words [0] .size (); unordered_map wordCnt; for (auto & word: words) + + wordCnt [word]; for (int I = 0; I wordCnt [t]) break } if (j = = n) res.push_back (I);} return res;}}

This problem also has a solution of O (n) time complexity, the design idea is very clever, but it is difficult to figure out, the blogger's visual observation has not yet reached this level. This method is no longer a traversal of a character, but a traversal of a word. For example, according to the example in the topic, the length of the string s is 18 cnt=2 words array, and the length of each word len is 3, then the traversal order is 0BEI 3BE6, 8PM 12J15, then offset one character 1pence4, 7JE7, 13, 16, and then offset another character 25. So that you can traverse all the situations, or first use a HashMap M1 to record all the words in words, and then traverse from 0, use left to record the position of the left boundary, and count represents the number of words that have been matched. Then the traversal of a word, if the word t currently traversed exists in M1, then add it to another HashMap m2. If the number in m2 is less than or equal to the number in M1, then count increases by 1. If it is greater than, some processing needs to be done, such as the following case: s = barfoofoo, words = {bar, foo, abc}, add a new abc to words, so that traversing to barfoo will not stop. When traversing to the second foo, m2 [foo] = 2, and M1 [foo] = 1, which is no longer continuous, so to move the position of the left boundary left, first take out the first word t1=bar, and then subtract m2 [T1] from 1, if at this time m2 [T1]

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.