**阅读更多**

# 1 Question-3[★★★]

**Longest Substring Without Repeating Characters**

Given a string, find the length of the longest substring without repeating characters.

1 | public class Solution { |

# 2 Question-5[★★★]

**Longest Palindromic Substring**

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

1 | public class Solution { |

# 3 Question-20[★★★★]

**Valid Parentheses**

Given a string containing just the characters

`'('`

,`')'`

,`'{'`

,`'}'`

,`'['`

and`']'`

, determine if the input string is valid.

The brackets must close in the correct order,

`"()"`

and`"()[]{}"`

are all valid but`"(]"`

and`"([)]"`

are not.

**错误的版本**

- 反例：
`[(])`

1 | public class Solution { |

**正确的版本**

1 | public class Solution { |

# 4 Question-22[★★★]

**Generate Parentheses**

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

1 | public class Solution { |

# 5 Question-28[★★★★]

这题可以由KMP算法解决

The algorithm is designed to improve upon the performance of traditional pattern-matching algorithms, such as the naïve approach or the brute-force method. The key idea behind the KMP algorithm is to avoid unnecessary character comparisons by utilizing information about the pattern itself.

Here’s a high-level overview of how the KMP algorithm works:

- Preprocessing (Building the “Partial Match” Table):

- The algorithm analyzes the pattern and constructs a “partial match” table, also known as the “failure function” or “pi function.”
- This table helps determine the number of characters to shift the pattern when a mismatch occurs during the search.

- Searching:

- The algorithm starts matching characters of the pattern against the text from left to right.
- If a character in the pattern matches the corresponding character in the text, both pointers are advanced.
- If a mismatch occurs:

- The algorithm uses the partial match table to determine the maximum number of characters it can safely skip in the pattern.
- It shifts the pattern by that amount and resumes matching from the new position, avoiding redundant comparisons.
By utilizing the partial match table, the KMP algorithm achieves a linear time complexity for pattern matching, specifically O(n + m), where n is the length of the text and m is the length of the pattern. This improvement makes it more efficient than the brute-force method, which has a time complexity of O(n * m).

The KMP algorithm is widely used in various applications that involve pattern matching, such as text editors, search engines, bioinformatics, and data mining, where efficient string searching is required.

It’s worth noting that while the KMP algorithm provides an efficient solution for pattern matching, it may not always be the optimal choice depending on the specific requirements and characteristics of the problem at hand. Other algorithms, such as Boyer-Moore or Rabin-Karp, may be more suitable in certain scenarios.

1 | class Solution { |

# 6 Question-32[★★★★]

**Longest Valid Parentheses**

Given a string containing just the characters

`'('`

and`')'`

, find the length of the longest valid (well-formed) parentheses substring.

For

`"(()"`

, the longest valid parentheses substring is`"()"`

, which has`length = 2`

.

**超时的版本**

1 | public class Solution { |

**改进后的版本**

1 | public class Solution { |

# 7 Question-49[★★★★]

**Group Anagrams**

Given an array of strings, group anagrams together.

For example, given:

`["eat", "tea", "tan", "ate", "nat", "bat"]`

1 | public class Solution { |