String problem¶
There are many string problems, from simple implementation of substr, recognition of palindrome, to more complex common substrings/subsequences. In fact, a string is essentially an array of characters, so Many data ideas and methods can also be used on string issues, and in some cases can play a very good role.
There are also many algorithms that specialize in processing strings, such as trie, horse-drawn cart algorithm, run-length encoding, huffman tree, and so on.
Some native methods to implement strings¶
This type of topic should be the most direct topic. The ambiguity of the topic is relatively small, and the difficulty is relatively small, so it is also good for forms such as electronic surface.
palindrome¶
A palindrome is a string with the same positive and negative readings, such as "level" or "noon", etc., which is a palindrome.
The general method for judging whether a palindrome is a double pointer at the beginning and the end. For details, see Question 125 below. The main idea of judging the longest palindrome is the two words "expansion", If you can make full use of the characteristics of palindrome, you can reduce a lot of unnecessary calculations, the typical "horse-drawn cart algorithm".
related question¶
- 5.longest-palindromic-substring
- 125.valid-palindrome
- 131.palindrome-partitioning
- 214.shortest-palindrome
- 516.longest-palindromic-subsequence
Prefix problem¶
The prefix tree is most intuitive to deal with this kind of problem, but it also has disadvantages, for example, when there are few common prefixes, it costs more memory.