0%

• 5. Longest Palindromic Substring
• 6. ZigZag Conversion
• 8. String to Integer (atoi)
• 14. Longest Common Prefix
• 28. Implement strStr()
• 58. Length of Last Word
• 125 . Valid Palindrome
• 131 . Palindrome Partitioning
• 132 . Palindrome Partitioning II
• 214 . Shortest Palindrome
• 336. Palindrome Pairs
• 796. Rotate String
• 816. Ambiguous Coordinates
• 819. Most Common Word ### 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, and there exists one unique longest palindromic substring.

C++

Java

Python

### 6. ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

C++

Java

### 8. String to Integer (atoi)

mplement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character ' ' is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

C++

Python

### 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

C++

Python

### 28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll" Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba" Output: -1

KMP标准模板题。O(m+n)

C++

Python

### 58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, Given s = "Hello World", return 5.

C++

Python

### 125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

C++

Python

### 131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab", Return

C++

Python

### 132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

dp。设dp[i]为[0,i]这个闭区间上的最少切割数。

• dp[i]=0 如果[o,i]为回文串
• dp[i] = min(dp[j-1]+1,dp[i]) ([j,i] 是回文串 1<=j<=i)

Python

C++ cheat OJ(主要是那个aaaa很长的字符)

C++

Java

Python

• dp[i + j +1 ]=min(dp[i + j + 1], dp[i - j] + 1)  奇数枚举
• dp[i + j + 1] = min(dp[i + j + 1 ], dp[i - j + 1] + 1)偶数枚举

C++

Python

### 214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

• aacecaaa => aaacecaaaacecaaa
• abcd => dcbaabcd

OK, 但是这样会有很多没必要的字符在里面。比如dcbaabcd中间冗余了一个a，我们需要去掉它，才能变为最短的回文串。

KMP的失配函数f[i]表示为当前字符应该去与哪个数比较。

[0, 0, 1, 0, 0, 0, 1, 2, 2, 0, 1, 2, 2, 3, 4, 5, 6, 7]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

C++

Python

### 336. Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1: Given words = ["bat", "tab", "cat"] Return [[0, 1], [1, 0]] The palindromes are ["battab", "tabbat"]

Example 2: Given words = ["abcd", "dcba", "lls", "s", "sssll"] Return [[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

PS：如果此题单词列表可以重复，可以把hash改成key - list的形式 ， python可以用collections.defaultdict(list)，然后先把答案存在key-set的结构中collections.defaultdict(set) 去重，最后返回list[list]

### 796. Rotate String

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1: Input: A = 'abcde', B = 'cdeab' Output: true

Example 2: Input: A = 'abcde', B = 'abced' Output: false

Note:

A and B will have length at most 100.

C++

Python

### 816. Ambiguous Coordinates

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)".  Then, we removed all commas, decimal points, and spaces, and ended up with the string S.  Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with less digits.  Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order.  Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1: Input: "(123)" Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

Example 2: Input: "(00011)" Output:  ["(0.001, 1)", "(0, 0.011)"] Explanation: 0.0, 00, 0001 or 00.01 are not allowed.

Example 3: Input: "(0123)" Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

Example 4: Input: "(100)" Output: [(10, 0)] Explanation: 1.0 is not allowed.

Note:

4 <= S.length <= 12. S[0] = "(", S[S.length - 1] = ")", and the other elements in S are digits.

• "0" 返回 ["0"]
• "0xxx0" 返回空
• "0xxxx" 返回["0.xxxx"]
• "xxxx0" 返回["xxxx0"]
• 其它的就返回每个切分点即可。

C++

Python 版本1

Python 版本2

### 819. Most Common Word

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words.  It is guaranteed there is at least one word that isn't banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation.  Words in the paragraph are not case sensitive.  The answer is in lowercase.

Example: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

• 1 <= paragraph.length <= 1000.
• 1 <= banned.length <= 100.
• 1 <= banned[i].length <= 10.
• The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
• paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
• Different words in paragraph are always separated by a space.
• There are no hyphens or hyphenated words.
• Words only consist of letters, never apostrophes or other punctuation symbols.

C++

Python