String matches in array

















You are given an array of strings, words, in which each string can be considered a word. Return all words in words that are substrings of other words in any order.

The string words[I] is a substring of words[j] if you can delete the leftmost and/or rightmost characters of words[j] to get word[I].

Example:
Input: words = [‘mass’,’as’,’hero’,’superhero’]
Output: [‘ as’ and ‘hero’]
Explanation: ‘as’ is a substring of ‘mass’ and ‘hero’ is a substring of ‘superhero’.
[‘hero’,’as’] are also valid answers.








For string matching problems, you can use the indexOf method in JavaScript to quickly determine substrings.

In the second traversal process, once the string that meets the requirements is found, the break statement is used to exit the loop in time to avoid unnecessary time consumption.

Time complexity O(n^2), space complexity O(n).










Query the array with keys

















You are given an array of queries. The elements in the array are positive integers between 1 and m. Please handle all queries[I] (from I =0 to I =queries.length-1) according to the following rules:

At first, the permutation P=[1,2,3… m].
For the current I, find the position of the item to be queried [I] in P (with subscripts starting from 0) and move it from the original position to the starting position of P (with subscripts 0). Note that the position of queries[I] in P is the result of queries[I].
Please return the result of the array queries as an array.

Example:
Enter: queries = [3,1,2,1], m = 5
Output:,1,2,1 [2]
Array queries are processed as follows:
For I =0: queries[I]=3, P=[1,2,3,4,5], P=[1, 1,2,4,5], P=[1, 1,2,4,5]
For I =1: queries[I]=1, P=[3,1,2,4,5], P=[1,3,2,4,5], P=[1,3,2,4,5]
For I =2: queries[I]=2, P=[1,3,2,4,5], P=[2,1,3,4,5]
For I =3: queries[I]=1, P=[2,1,3,4,5], P=[1,2,3,4,5], P=[1,2,3,4,5]
Therefore, the result array returned is [2,1,2,1].








Basic operations on arrays

Time complexity O(n^2), space complexity O(n).










HTML entity parser

















An “HTML Entity parser” is a special parser that takes HTML code as input and replaces all of these special character entities with the characters themselves.

These special characters and their corresponding character entities in HTML include:

Double quotation marks: The character entity is “and the corresponding character is”.
Single quotation mark: The character entity is’ and the corresponding character is’.
Ampersand: the character entity is ampersand and the corresponding character is ampersand.
Greater than sign: the character entity is > and the corresponding character is >.
Less than sign: the character entity is < and the corresponding character is <.
Slash number: The character entity is ⁄ and the corresponding character is /.
Given the string text, you implement an HTML entity parser that returns the parsed results.

Example:
Enter: text = ‘& is an HTML entity but &ambassador; is not.’
Output: ‘& is an HTML entity but &ambassador; is not.’
Explanation: The parser replaces the character entity & with &








This problem mainly examines the string matching, here can use JavaScript replace method combined with the regular to complete the replacement of the target string.










Number of schemes for coloring N x 3 grids

















If you have an N x 3 grid, you need to color each grid with one of three colors: red, yellow, and green. Make sure that adjacent grids are different colors (i.e. cells with the same horizontal or vertical edges).

Give you the number of lines in the grid, n.

Return the number of schemes to color the grid. Since the answer can be very large, return the answer mod 10^9 + 7.

Example:
Enter n = 1
Output: 12
Explanation: There are 12 possible methods








Since it is an N * 3 grid, there are only the 12 cases mentioned above in the horizontal direction. Then, the coloring of the next layer should be calculated according to the above conditions, that is, considering the different colors of adjacent grids in the vertical direction.

There are five scenarios for the next level of the ABA pattern.

There are four scenarios for the next level of ABC pattern.

Here, it can be seen that for N * 3 grid, the number of coloring schemes should be determined by the number of ABA and ABC in (n-1) * 3 grid, so this problem can be solved by dynamic programming.

Take a closer look at the above two figures and you can get the state transition equations of ABA and ABC:

  • aba(n) = aba(n – 1) * 3 + abc(n – 1) * 2

  • abc(n) = aba(n – 1) * 2 + abc(n – 1) * 2

Time complexity O(n), space complexity O(1).










Highlights from the past






  • LeetCode Tour for front End Engineers – Week 183

  • LeetCode Tour for front End Engineers — Week 182

  • Front End Engineer’s LeetCode Journey — Week 181

  • LeetCode Tour for front End Engineers — Week 180

  • LeetCode Tour for front End Engineers – Week 179

  • JavaScript AC solutions to problems on LeetCode