字符串基础题
原创
总结：所有题目都已做，有些Easy没有做第二遍，有两道没有accept，请戳 link-en, link-cn
一、滑动窗口
滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
int left = 0, right = 0;
// 先移动 right 寻找可行解
while (right < s.size()) {
window.add(s[right]);
right++;
// 找到(不)可行解后，开始移动 left 缩小窗口
while (valid) {
window.remove(s[left]);
left++;
}
}两种：
1. 是初始已经可行，是向右一直寻找最大可行解，当不可行了就while(not_valid)left++缩小窗口直到再次可行更新解
2. 初始不可行，向右寻找可行，当可行了就while(valid)left++缩小窗口直到再次找到不可行(之前更新解)，再向右增大窗口
76. 最小覆盖子串 - M
https://leetcode.com/problems/minimum-window-substring/
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"Note:
- If there is no such window in S that covers all characters in T, return the empty string "".
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Solution
from collections import Counter, defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t: return ""
start, end = 0, 0
res, min_len = "", float("inf")
t_c = Counter(t)
s_c = defaultdict(int)
while end < len(s):
s_c[s[end]] += 1
end += 1
while all(map(lambda x: s_c[x] >= t_c[x], t_c.keys())):
if min_len>end-start:
res = s[start:end]
min_len = end-start
s_c[s[start]] -= 1
start += 1
return res思路看模板
待做：不用counter的方法(Refer)，counter太难记了
3+. 无重复字符的最长子串 - M
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string, find the length of thelongest substringwithout repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Solution
from collections import defaultdict
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) <= 1: return len(s)
window = defaultdict(int)
max_len = 0
start, end = 0, 0
while end < len(s):
window[s[end]] += 1
while window[s[end]] > 1:
window[s[start]] -= 1
start += 1
end += 1
max_len = max(max_len, end-start)
return max_len知道思路了就是很简单的题，但是debug了一个小时吧一直各种出错，再做一遍吧
340. 至多包含 K 个不同字符的最长子串 - H
Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2,
T is "ece" which its length is 3.
Example 1:
输入: "A man, a plan, a canal: Panama"
输出: trueExample 2:
输入: s = "aa", k = 1
输出: 2
解释: 则 T 为 "aa"，所以长度为 2。Solution
from collections import defaultdict
class Solution(object):
def lengthOfLongestSubstringKDistinct(self, s, k):
if len(s) <= k : return len(s)
start, end = 0, 0
res = 0
di = defaultdict(int)
while end < len(s):
di[s[end]] += 1
while len(di.keys()) > k:
di[s[start]] -= 1
# 记得pop if value == 0
if not di[s[start]]: di.pop(s[start])
start += 1
end += 1
res = max(res, end-start)
return res自己的思路自己做的，但是漏了pop掉value为0的key
On时间，Ok空间
395. 至少有K个重复字符的最长子串
Longest Substring with At Least K Repeating Characters
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.Example 2:
Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.Solution
from collections import defaultdict
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
res = 0
start, end = 0, 0
for start in range(len(s)):
di = defaultdict(int)
for end in range(start, len(s)):
di[s[end]] += 1
end += 1
if all(map(lambda x:di[x]>=k, di.keys())):
res = max(end-start, res)
return res非常丑陋，冥冥之中感觉有更好的解法，一开始用滑动窗口做，错了，做成了最短包含K重复，和340题搞混了
二、 DP
二维DP初始化很重要，初始化空串情况
动态规划思路：明确dp数组的含义；写状态转移方程；定义base case(非常重要!!)
5. 最长回文子串 - M
Given a strings, find the longest palindromic substring ins. You may assume that the maximum length ofsis 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.Example 2:
Input: "cbbd"
Output: "bb"Solution
要分析清楚二维dp的对状态转移的依赖，dp[i][j] = dp[i+1][j-1]的情况，要for j再for i，这样dp[i+1][j-1]就已经被赋值
class Solution(object):
def longestPalindrome(self, s):
if len(s) <= 1: return s
res = s[0]
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
dp[0][0] = True
for r in range(1, len(s)):
for l in range(r):
if s[l] == s[r] and (r-l <= 2 or dp[l+1][r-1]):
dp[l][r] = True
#更新结果
if dp[l][r]:
res = s[l:r+1] if r-l >= len(res) else res
return res1143. 最长公共子序列 - M
Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.Constraints:
- 1 <= text1.length <= 1000
- 1 <= text2.length <= 1000
- The input strings consist of lowercase English characters only.
Solution
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]
for i in range(1,len(text1)+1):
for j in range(1, len(text2)+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]没啥问题，优秀的我自己写的
注意：初始化很重要，这里要从空串开始初始化，方便计算
91. 解码方法
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).Solution
dp[i] = dp[i-1] + dp[i-2] (有条件的)
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == "0": return 0
dp = [1] + [0]*(len(s)-1)
if len(s) == 1: return dp[-1]
if s[1] != "0":
dp[1] += 1
if 10<=int(s[:2])<=26:
dp[1] += 1
for i in range(2, len(s)):
if s[i-1:i+1] == "00": return 0
if s[i] != "0":
dp[i] += dp[i-1]
if 10<=int(s[i-1:i+1])<=26:
dp[i] += dp[i-2]
return dp[-1]三、其他高频题
28. 实现 strStr() - E
https://leetcode.com/problems/implement-strstr/
ImplementstrStr().
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: 2Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
Solution
思路：两种解法，暴力法O((m-n)*n)没必要；KMP
待做：KMP，Reference
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
for i in range(len(haystack) - len(needle)+1):
if haystack[i:i+len(needle)] == needle:
return i
return -114. 最长公共前缀 - E
https://leetcode.com/problems/longest-common-prefix/
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.Note:
All given inputs are in lowercase letters a-z.
Solution -1
class Solution:
def longestCommonPrefix(self, strs):
res = ""
for z in zip(*strs):
if len(set(z)) == 1:
res += z[0]
else: break
return res抄的，zip(*)这个有点不是很明白，zip使用
思路：zip所有string，set所有第i个char，set后数量为1则是common prefix
Solution - 2
class Solution:
def longestCommonPrefix(self, strs):
if not strs: return ""
res = ""
strs.sort()
fir, la = strs[0], strs[-1]
for i in range(len(fir)):
if i < len(la) and fir[i] == la[i]:
res += fir[i]
else: break
return ressort(strs)，第一个和最后一个的common prefix则为整个序列的common prefix
125. 验证回文串 - E
https://leetcode.com/problems/valid-palindrome/
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: "A man, a plan, a canal: Panama"
Output: trueExample 2:
Input: "race a car"
Output: falseSolution
双指针：一个从后往前，一个从前往后，一个一个匹配
class Solution:
def isPalindrome(self, s: str) -> bool:
if len(s) <= 1: return True
start, end = 0, len(s)-1
while start<end:
while start < len(s) and not s[start].isalnum():
start += 1
while end >= 0 and not s[end].isalnum():
end -= 1
if start>end: return True
if s[start].upper() != s[end].upper(): return False
start += 1
end -= 1
return True49. 字母异位词分组 - M
https://leetcode.com/problems/group-anagrams/
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
Solution
Sort每个string，dict count
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
di = defaultdict(list)
for s in strs:
# key code
di["".join(sorted(s))].append(s)
return list(di.values()) 四、其他杂题
8. 字符串转换整数 (atoi) - M
Implement atoi which converts a string to an integer.
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:
Input: "42"
Output: 42Example 2:
Input: " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.Example 3:
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.Example 4:
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.Example 5:
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.Solution
注意：except: break; outOfRange control
class Solution:
def myAtoi(self, str: str) -> int:
str = str.lstrip()
if not str: return 0
res = 0
idx = 2 if str[0] in ["-","+"] else 1
while idx <= len(str):
try:
res = int(str[:idx])
idx += 1
except:
break
if res > 2147483647: return 2147483647
if res < -2147483648: return -2147483648
return res227. 基本计算器 II
Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2*2"
Output: 7Example 2:
Input: " 3/2 "
Output: 1Example 3:
Input: " 3+5 / 2 "
Output: 5Note:
- You may assume that the given expression is always valid.
- Do not use the eval built-in library function.
Solution
先算乘除，最后算加减
class Solution(object):
def calculate(self, s):
stack = []
idx, res = 0, 0
while idx < len(s):
# 数字
if s[idx].isdigit():
num = 0
while idx<len(s) and s[idx].isdigit():
num = num*10+int(s[idx])
idx += 1
stack.append(num)
#数字添加结束就看能不能算乘除
while len(stack)>=2 and stack[-2] in ["*", "/"]:
stack.pop()
opt = stack.pop()
if opt == "*":
stack.append(stack.pop() * num)
else:
stack.append(stack.pop() // num)
# 符号
elif s[idx] in ["*", "/", "+", "-"]:
stack.append(s[idx])
idx += 1
# 其他
else:
idx += 1
# 开始算加减
opt = 1
for ch in stack:
if ch == "+":
opt = 1
elif ch == "-":
opt = -1
else:
res += opt * ch
return res
10.24 调了半天还是没能bug free
11.7 看了思路，写了，抄了，懂了
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。