六. 字符串
14. 最长公共前缀
题目：编写一个函数来查找字符串数组中的最长公共前缀。
输入：strs = ["flower","flow","flight"]
输出："fl"
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0: # 字符串数组为空
return ""
if len(strs) == 1: # 字符串数组只有一个元素
return strs[0]
for j in range(0, len(strs[0])): # 第一个元素的0~j位
for i in range(1, len(strs)): # 0~i个元素
if len(strs[i])>=j+1:
if strs[0][j] != strs[i][j]:
return strs[0][0: j] # 一旦返现第j位有异样，返回0到j-1位
if (j == len(strs[0])-1 and i == len(strs)-1):
return strs[0][0:j+1] # 循环到最后都满足，返回第0个字符串
else:
return strs[0][0: j]
return ""
28. 实现 strStr()
题目：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
输入：haystack = "hello", needle = "ll"
输出：2
思考：KMP问题。
def strStr(self, haystack: str, needle: str) -> int:
a = len(needle)
b = len(haystack)
if a == 0:
return 0
next = self.getnext(a, needle)
p = -1
for j in range(b):
while p >= 0 and needle[p+1] != haystack[j]:
p = next[p]
if needle[p+1] == haystack[j]:
p += 1
if p == a-1:
return j-a+1
return -1
def getnext(self, a, needle):
next=['' for i in range(a)]
k = -1
next[0] = k
for i in range(1,len(needle)):
while (k >- 1 and needle[k+1] != needle[i]):
k = next[k]
if needle[k+1] == needle[i]:
k += 1
next[i] = k
return next
58. 最后一个单词的长度
题目：最后一个单词的长度
输入：s = "Hello World"
输出：5
def lengthOfLastWord(self, s: str) -> int:
flag = 0 # 0 表示还没遇到字母, 第一次遇到字母后置1
count = 0
for x in s[::-1]:
if x == " " and flag == 0:
count = 0
elif x == " " and flag == 1:
return count
else:
flag = 1 # 冗余
count += 1
return count
125. 验证回文串
题目：验证回文串
def isPalindrome(self, s: str) -> bool:
sgood = "".join(ch.lower() for ch in s if ch.isalnum()) # 去除空格和符号
n = len(sgood)
left, right = 0, n - 1
while left < right: # 左右逼近
if sgood[left] != sgood[right]:
return False
left, right = left + 1, right - 1
return True
205. 同构字符串
题目：同构字符串
输入：s = "egg", t = "add"
输出：True
def isIsomorphic(self, s: str, t: str) -> bool:
ds = dict()
dt = dict()
for i in range(0, len(s)):
if s[i] in ds: # 存在，检查ds
if t[i] != ds[s[i]]:
return False
elif t[i] in dt: # 存在，检查dt
if s[i] != dt[t[i]]:
return False
else: # 不存在，则更新ds和dt
ds[s[i]] = t[i]
dt[t[i]] = s[i]
return True
