string.capitalize() 第一個(gè)字符大寫
string.count(str, beg=0, end=len(string)) 返回 str 在 string 里面出現(xiàn)的次數(shù)，beg 、 end 指定范圍
string.endswith(obj, beg=0, end=len(string)) 檢查字符串是否以 obj 結(jié)束
string.find(str, beg=0, end=len(string)) 返回str開始的索引值，否則返回-1
string.index(str, beg=0, end=len(string)) 跟find()方法一樣夕土，只不過如果str不在 string中會(huì)報(bào)一個(gè)異常.
string.isalnum() string 至少有一個(gè)字符并且所有字符都是字母或數(shù)字則返回 True
string.isalpha() string 至少有一個(gè)字符并且所有字符都是字母則返回 True
string.isdecimal() string 只包含十進(jìn)制數(shù)字則返回 True
string.isdigit() string 只包含數(shù)字則返回 True
string.islower() string 都是小寫呐馆，則返回 True
string.isnumeric() string 中只包含數(shù)字字符臼隔，則返回 Tru
string.isspace() string 中只包含空格遂唧，則返回 True
string.istitle() string 是標(biāo)題化的(見 title())則返回 True
string.isupper() string 都是大寫如输，則返回 True
string.join(seq) 以 string 作為分隔符有鹿，將 seq 中所有的元素(的字符串表示)合并為一個(gè)新的字符串
string.lower() 轉(zhuǎn)換 string 中所有大寫字符為小寫.
string.lstrip() 截掉 string 左邊的空格
max(str) 返回字符串 str 中最大的字母旭旭。
min(str) 返回字符串 str 中最小的字母。
string.replace(str1, str2, num=string.count(str1)) 把 string 中的 str1 替換成 str2,替換不超過 num 次.
string.split(str="", num=string.count(str)) 以 str 為分隔符切片 string葱跋，僅分隔 num+ 個(gè)子字符串
string.startswith(obj, beg=0,end=len(string)) 檢查字符串是否是以 obj 開頭持寄，是則返回 True
string.strip([obj]) 在 string 上執(zhí)行 lstrip()和 rstrip()
string.swapcase() 翻轉(zhuǎn) string 中的大小寫
string.title() 返回"標(biāo)題化"的 string,就是說所有單詞都是以大寫開始，其余字母均為小寫(見 istitle())
string.translate(str, del="") 根據(jù) str 給出的表(包含 256 個(gè)字符)轉(zhuǎn)換 string 的字符,要過濾掉的字符放到 del 參數(shù)中
string.upper() 轉(zhuǎn)換 string 中的小寫字母為大寫
字符串
給定一個(gè)字符串娱俺，驗(yàn)證它是否是回文串稍味，只考慮字母和數(shù)字字符，可以忽略字母的大小寫荠卷。
說明：本題中模庐，我們將空字符串定義為有效的回文串。
輸入: "A man, a plan, a canal: Panama"
輸出: true
逆字符串
class Solution:
def isPalindrome(self, s: str) -> bool:
alnum = ''.join(w.lower() for w in s if w.isalnum())
return alnum == alnum[::-1]
使用雙指針油宜。初始時(shí)掂碱，左右指針分別指向兩側(cè)怜姿，隨后我們不斷地將這兩個(gè)指針相向移動(dòng)，每次移動(dòng)一步疼燥，并判斷這兩個(gè)指針指向的字符是否相同沧卢。當(dāng)這兩個(gè)指針相遇時(shí)，就說明是回文串醉者。
class Solution:
def isPalindrome(self, s: str) -> bool:
pre = 0
nex = len(s) - 1
while pre < nex:
# 找到下一個(gè)字母或數(shù)字
while pre < nex and not s[pre].isalnum(): # 忽略非字母數(shù)字
pre += 1
while pre < nex and not s[nex].isalnum(): # 忽略非字母或數(shù)字
nex -= 1
# 判斷
if pre < nex:
if s[pre].lower() != s[nex].lower(): # 忽略大小寫
return False
pre += 1
nex -= 1
return True
給定一個(gè)字符串 s但狭，將 s 分割成一些子串，使每個(gè)子串都是回文串湃交。
返回 s 所有可能的分割方案熟空。
示例:
輸入: "aab"
輸出:
[ ["aa","b"], ["a","a","b"] ]
實(shí)現(xiàn)一個(gè) Trie (前綴樹)藤巢，包含 insert, search, 和 startsWith 這三個(gè)操作搞莺。
Trie 是一顆非典型的多叉樹模型
一般的多叉樹的結(jié)點(diǎn)是這樣的：
struct TreeNode {
VALUETYPE value; //結(jié)點(diǎn)值
TreeNode* children[NUM]; //指向孩子結(jié)點(diǎn)
};
而 Trie 的結(jié)點(diǎn)是這樣的(假設(shè)只包含'a'~'z'中的字符)：
struct TrieNode {
bool isEnd; //該結(jié)點(diǎn)是否是一個(gè)串的結(jié)束
TrieNode* next[26]; //字母映射表
};
這時(shí)字母映射表next 的妙用就體現(xiàn)了，TrieNode* next[26]中保存了對(duì)當(dāng)前結(jié)點(diǎn)而言下一個(gè)可能出現(xiàn)的所有字符的鏈接掂咒，因此我們可以通過一個(gè)父結(jié)點(diǎn)來預(yù)知它所有子結(jié)點(diǎn)的值：
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
說明:
你可以假設(shè)所有的輸入都是由小寫字母 a-z 構(gòu)成的才沧。
保證所有輸入均為非空字符串。
給定一個(gè)二維網(wǎng)格 board 和一個(gè)字典中的單詞列表 words绍刮，找出所有同時(shí)在二維網(wǎng)格和字典中出現(xiàn)的單詞温圆。
單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成孩革，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格岁歉。同一個(gè)單元格內(nèi)的字母在一個(gè)單詞中不允許被重復(fù)使用。
輸入:
words = ["oath","pea","eat","rain"]
board =
[ ['o','a','a','n'],
['e', 't', 'a', 'e'],
['i', 'h', 'k', 'r'],
['i', 'f', 'l', 'v'] ]
輸出: ["eat","oath"]
給定兩個(gè)字符串 s 和 t 膝蜈，編寫一個(gè)函數(shù)來判斷 t 是否是 s 的字母異位詞锅移。
輸入: s = "anagram", t = "nagaram"
輸出: true
逐個(gè)去除b里的a中字符
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
s = list(s)
t = list(t)
for i in s:
try:
t.remove(i)
except ValueError as e:
return False
return True
第一次循環(huán)哈希表記錄，第二次循環(huán)刪去哈希表記錄饱搏，最后統(tǒng)計(jì)哈希表每個(gè)值是否都為0
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
word_count = {}
# 建立哈希表
for i in s:
if i not in word_count:
word_count[i] = 1
else:
word_count[i] += 1
# 清空哈希表
for i in t:
if i in word_count:
word_count[i] -= 1
else:
return False
# all([]) ture any([]) false
return not any(list(word_count.values()))
給定一個(gè)字符串非剃，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引推沸。如果不存在备绽，則返回 -1。
哈希表記錄每個(gè)字符出現(xiàn)次數(shù)
class Solution:
def firstUniqChar(self, s: str) -> int:
# count = collections.Counter(s)
word_count = {}
# 建立哈希表
for i in s:
if i not in word_count:
word_count[i] = 1
else:
word_count[i] +=1
# 根據(jù)哈希表判斷出現(xiàn)次數(shù)
for index, word in enumerate(s):
if word_count[word] == 1:
return index
return -1
編寫一個(gè)函數(shù)鬓催，其作用是將輸入的字符串反轉(zhuǎn)過來肺素。輸入字符串以字符數(shù)組 char[] 的形式給出。
# s[:]=s[::-1]
# 雙指針
l,r=0,len(s)-1
while l<r:
s[l],s[r]=s[r],s[l]
l+=1
r-=1
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"宇驾，所以其長度為 3压怠。
使用數(shù)組作為滑動(dòng)窗口
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s: return 0
substr = []
max_len = 0
for word in s:
if word not in substr:
# 擴(kuò)展窗口
substr.append(word)
else:
# 從窗口中移除重復(fù)字符及之前的字符串部分
substr = substr[substr.index(word)+1:]
# 擴(kuò)展窗口
substr.append(word)
max_len = max(max_len, len(substr))
return max_len
法1中容器的伸縮涉及內(nèi)存分配,所以方法2換成位置指針省掉了內(nèi)存分配
直觀的滑動(dòng)窗口方法需要維護(hù)數(shù)組的增刪，實(shí)際上比較耗時(shí)飞苇。使用雙指針（索引）菌瘫，記錄滑動(dòng)窗口起始和結(jié)束的索引值蜗顽，可以減除數(shù)組增刪操作，提高效率雨让，使用指針位移以及從原數(shù)組中截取雇盖，代替原來的窗口元素增刪操作
def lengthOfLongestSubstring(self, s: str) -> int:
# 字符串為空則返回零
if not s: return 0
max_len = 0
left_index, right_index = 0, 0 # 雙指針
for word in s:
# 如果字符不在滑動(dòng)窗口中，則直接擴(kuò)展窗口
if word not in s[left_index:right_index]:
# 右指針右移一位
right_index += 1
else:
# 左指針右移 word在substr中的索引 位
left_index += s[left_index:right_index].index(word) + 1
# 右指針右移一位
right_index += 1
max_len = max(right_index - left_index, max_len)
return max_len
Hash（字典）栖忠，滑動(dòng)窗口崔挖，雙指針
使用字典記錄任意字符最近的索引值，字典查詢時(shí)間復(fù)雜度為O(1)庵寞，相比數(shù)組查詢狸相，效率更高
該算法的難點(diǎn)在于理解word_index[word] > ignore_end_index如果不大于說明word已經(jīng)被丟棄；大于說明word未被丟棄需要捐川，更新ignore_end_index
def lengthOfLongestSubstring(self, s: str) -> int:
ignore_end_index = -1 # 指向子串左邊一個(gè)字符脓鹃，即丟棄的子串的尾部， 初始值為 -1古沥，還沒有開始移動(dòng)
max_len = 0 # 記錄最大的長度
word_index = {} # 滑動(dòng)窗口瘸右，任意字符最后出現(xiàn)位置的索引
for index, word in enumerate(s):
# 如果 word出現(xiàn)過 且 最近一次出現(xiàn)的索引大于ignore_end，意味著需要丟棄這個(gè)詞前面的部分
# 如果不大于說明word已經(jīng)被丟棄岩齿；大于說明word未被丟棄需要太颤，更新ignore_end_index
if word in word_index and word_index[word] > ignore_end_index:
ignore_end_index = word_index[word] # 新的子串開始
word_index[word] = index # 更新word的索引
else:
# word未出現(xiàn)過
word_index[word] = index # 子串變長
max_len = max(max_len, index - ignore_end_index) # 更新最大長度
return max_len
