leetcode 字符串

本次题解包括

  • 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.

题目地址:leetcode Longest Palindromic Substring

题意:给定一个字符串S,求一个S的最长子回文串。

思路:最朴素的思想是枚举开头,枚举结尾,判断是否回文,复杂度太高。

我们可以只枚举开头和长度,这样只要O(N^2)

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".

题目地址:leetcode ZigZag Conversion

题目大意:给定一个zigzag 写法的字符串,要你恢复它

思路:

从上往下,然后从下往上即可。。

C++

Java

无聊写了个找规律的版本,就是先找好第i行下一个间距。。

 


 

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:

题目地址:leetcode String to Integer (atoi)

题目大意:给定一个字符串,要你转成int

思路:好好的看题目跟着做即可。

C++

Python

 


 

14. Longest Common Prefix

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

题目地址:leetcode Longest Common Prefix

题目大意: 给一个数组,数组中每个元素都是字符串,求他们的最长公共前缀

思路:

把第一个作为ans,然后和后面的依次比较即可。

注意点:ans和strs[i]的长度关系。

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

题目地址:leetcode Implement strStr()

题目大意:给定两个字符串haystack 和 needle,求needle在haystack中出现的初始位置。

思路:

简单的暴力枚举O(mn)不说了

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.


题目地址:leetcode Length of Last Word

题目大意: 给定字符串,求最后一个单词的长度。单词和单词间用空格隔开,若不存在,返回0

思路: 从右向左扫描,扫描到第一个字母为止,记为j。然后从j向左扫描,找到第一个空格为止。这样长度为j – i

C++

Python

用split

 

 

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.

题目地址:leetcode Palindrome Partitioning

题意:给定一个字符串,判断其是否是回文串

思路:注意大小写转化和标点符号

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

题目地址:leetcode Palindrome Partitioning II

题意:给定一个字符串,要求将其划分,使得每个字串都是回文串。

思路:DFS

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.

题目地址:leetcode Palindrome Partitioning II

题意:给定一个字符串,问最少切几刀,能使该字符串分割为若干个字符串,且每个字符串都是回文串。

思路:

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

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

这样写出了如下py代码,1A,但是速度很慢!而且翻译成C++ TLE!

Python

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

 

于是改进,还记得第5题么?

当时我们是枚举了起始位置和长度,降低了复杂度。

这题也一样。

我们枚举k为当前计算的位置,然后用双指针的思想,从k向两边扩散,判断是否回文(要分别计算长度为奇数和偶数的情况),并根据上述公式更新dp数组。这样,就可以将第一种解法的枚举j和判断回文合并起来,从而把复杂度降低为O(n^2)

C++

Java

Python

 

另一种写法:

设dp[i]为dp[0,i-1]上的最少分割数

  • 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".

题目地址 leetcode Shortest Palindrome

题意:给定一个字符串,在它前面添加若干个字符,使其变成回文串(要求最短)

思路:

我们知道,对于任意的字符串,不管它是不是回文串,我们将其翻转在添加到原串上,它一定是回文串。

比如题目中的

  • aacecaaa => aaacecaaaacecaaa
  • abcd => dcbaabcd

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

怎么去掉呢?其实去掉的过程就是求原串s的前缀在其逆序的revs中最长能匹配的后缀长度。

这里用到了KMP里的失配函数。

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

如果我们将s翻转为revs,然后将s链接上revs(为了避免两个串混起来,在中间加上了’#’也就是 s + ‘#’ + revs),然后求失配函数。这样,就可以求出前缀在后缀中匹配了多少个字符!而剩下不匹配的就是我们要添加的字符啦。

比如:

比如,题目中的aacecaaa 变为了  aacecaaa#aaacecaa它的失配函数值为:

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

也就是说,最后前后缀匹配了7个(已经加粗),我们只需要添加1个字符进去就可以了。 这个字符就是revs的第一个字符

再比如,题目中的abcd变为了abcd#dcba, 失配函数值为:

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

最后前后缀只匹配了1个数(已经加粗),说明我们需要添加3个数进去。

 

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"]

题目地址:leetcode Palindrome Pairs

题意:给定一个单词列表(每个单词均唯一),求所有的i,j(i !=j) 使得words[i] + words[j] 是回文串

思路:暴力的方法是直接对枚举所有可能的情况,然后看看是否回文串。

改进的方法是用hash,首先将所有的单词作为Key,相应的value为它的下标。

接着对于每个单词x,枚举i(从[0,len(word) ),将其分为左右两边(前缀和后缀 )。

对于后缀suffix,我们可以把它逆序r_suffix,看看字典中是否存在这个单词y,若存在,则判断 r_suffix + x 是否为回文串(后缀逆序后加原单词前看看是否回文,前缀则加后面,可以看看214题)

同样对于前缀prefix,逆序为r_prefix,字典中存在的话,则判断 x + r_prefix是否为回文串。

此外要注意单词为””的情况。

根据上述思路,写下如下代码:

然而上述的思路仍有改进的地方

比如,划分的时候,对于前缀prefix,它是要逆序加在原单词后面的,这部分一定是相同的,没必要重复比较,我们只需要看看后缀是否回文。 后缀的时候也一样,只需看看前缀是否回文

此外,枚举i的范围从[0,len(word) ) 变为 [0,len(word)],这样就把 “”的情况考虑到了

 

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.

题目地址:leetcode Rotate String

题目大意:给定两个字符串A和B,让你判断B是否能由A循环左移得到

思路:

暴力枚举起点i (就是把i移动到初始位置)然后看看和B是否相同。复杂度O(n^2)

其实这个过程和在A+A中寻找B是一样的。因此写成一行:

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.

题目地址:leetcode Ambiguous Coordinates

题目大意:给定一个前后为括号,中间为数字的字符串,要求将中间的数字划分为左右两部分,左右两部分的数字必须是最简的,即不能有额外的0,比如0.0、01是不行的。

思路:枚举左右两边的分割点,然后可以分别对左右两边加入小数点再判断是否合法,也可以直接生成合法的:

  • “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.

题目地址:leetcode Most Common Word

题目大意:给定一个字符串段落和一个banned数组,求段落中出现频率最高的单词(单词不能在banned中出现)

思路:分词好后计数即可。

C++

Python

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 字符串
本文地址:https://www.hrwhisper.me/leetcode-string/

打赏一杯咖啡钱呗

Leetcode , . permalink.

6 thoughts on “leetcode 字符串

  1. 最后一个回文对, 能不能把所有字串拷贝反序后插入一个前缀树。 然后用每个原词查这个树。 如果有部分匹配的情况查剩下的部分是否回文。

  2. 哈哈我又来评论了,Palindrome Partitioning II这一题,我用DFS加记忆化搜索貌似时间上还过得去,你如果有空也写个贴上来呗,想学习一下你的代码风格

Leave a Reply

Your email address will not be published. Required fields are marked *