1、无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
# substr 向右扩展一个元素，如果该元素已经在 substr 中，则需要将其及其前面的元素去掉。
# 可通过 substr.index(c) 定位元素 或 substr.split(c)[1]分割成子串
# 发现有重复字符时，可以直接把左指针移动到第一个重复字符的下一个位置即可。
def lengthOfLongestSubstring(s: str) -> int:
# substr = ''
# maxlen = start = 0
# for i, c in enumerate(s):
# if c in substr: start += substr.index(c) + 1
# substr = s[start:i + 1]
# maxlen = max(i + 1 - start, maxlen)
substr = ''
maxlen = 0
for c in s:
if c in substr: substr = substr.split(c)[1]
substr += c
maxlen = max(len(substr), maxlen)
return maxlen
if __name__ == '__main__':
assert lengthOfLongestSubstring("abcabcbb") == 3
assert lengthOfLongestSubstring("pwwkewa") == 4
assert lengthOfLongestSubstring("bbbbb") == 1
assert lengthOfLongestSubstring("abba") == 2
assert lengthOfLongestSubstring("tmmzuxt") == 5
assert lengthOfLongestSubstring("") == 02、有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
def isValid(s):
if not s:return True
# lenth = len(s)
# if lenth%2:return False
brackets={'(':')','{':'}','[':']'}
# for i in brackets:
# if s.count(i)!=s.count(brackets[i]):return False
x=[]
for i in s:
if i in brackets: x.append(i)
else:
if x and i == brackets[x[-1]]:x.pop()
else:return False
else:
return not x # False if x else True
if __name__ == '__main__':
assert isValid("()") == True
assert isValid("()[]{}") == True
assert isValid("(]") == False
assert isValid("([)]") == False
assert isValid("{[]}") == True3、电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
# 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
from typing import List
# 字典快点
# numchar=['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
n = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
def letterCombinations(digits: str) -> List[str]:
if not digits: return []
# 定义函数 backtrack(combination, nextdigit)，
# 当 nextdigit 非空时，对于 nextdigit[0] 中的每一个字母 letter，
# 执行回溯 backtrack(combination + letter,nextdigit[1:]，
# 直至 nextdigit 为空。最后将 combination 加入到结果中。
def backtrack(conbination, nextdigit):
if nextdigit:
for letter in n[nextdigit[0]]:
# for letter in n[int(nextdigit[0])-2]:
backtrack(conbination + letter, nextdigit[1:])
else:
res.append(conbination)
res = []
backtrack('', digits)
return res
# 我们也可以使用队列，先将输入的 digits 中第一个数字对应的每一个字母入队，
# 然后将出队的元素与第二个数字对应的每一个字母组合后入队...
# 直到遍历到 digits 的结尾。最后队列中的元素就是所求结果。
def letterCombinations1(digits: str) -> List[str]:
if not digits: return []
queue = [''] # 初始化队列
for digit in digits:
for _ in range(len(queue)):
tmp = queue.pop(0)
# 这里我们不使用 int() 转换字符串，使用ASCII码
# for letter in n[ord(digit) - 50]:
for letter in n[digit]:
queue.append(tmp + letter)
return queue
def df(digits):
if not digits:return []
def x(res,d):
return x([i+j for i in res for j in n[d[0]]],d[1:]) if d else res
return x([''],digits)
def f(digits):
if not digits:return []
def func(r,d):
return func([i+j for i in r for j in d[0]],d[1:]) if d else r
return func([''],[n[x] for x in digits])
if __name__ == '__main__':
assert letterCombinations('23') == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
assert letterCombinations('') == []
assert letterCombinations('2') == ["a", "b", "c"]
assert df('23') == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
assert df('') == []
assert df('2') == ["a", "b", "c"]
assert f('23') == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
assert f('') == []
assert f('2') == ["a", "b", "c"]