出门了几天,没机会摸电脑...LintCode上看到阶梯训练,打算了解一下。
78. 最长公共前缀
给k个字符串,求出他们的最长公共前缀(LCP)
样例
在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"
在"ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"
这个题,先写个求公共前缀的函数供调用:
结果字符串设为空,取较短字符串长度,
defgetCommon(self,strA,strB):
lenA = len(strA)
lenB = len(strB)
result =''
length = min(lenA,lenB)
比较两个字符串前缀,相同的添加到结果末尾,如果不相同,返回结果,如果比较完较短的字符串,返回结果字符串。
foriinrange(length):
ifstrA[i]==strB[i]:
result = result + strA[i]
else:
returnresult
returnresult
longestCommonPrefix函数中,如果字符串为空,返回‘’
deflongestCommonPrefix(self,strs):
# write your code here
iflen(strs)==:
return''
结果字符串先设为第一个字符串,调用getCommon与之后的字符串进行比较,取结果继续与后面的字符串比较。返回最终结果。
result = strs[]
length = len(strs)
foriinrange(1,length):
print(result)
result =self.getCommon(result,strs[i])
returnresult
运行结果:
代码:
79. 最长公共子串
给出两个字符串,找到最长公共子串,并返回其长度。
样例
给出A=“ABCD”,B=“CBCE”,返回 2
如果A B长度均为0,返回0,如果A B中某一个为0,也返回0。
deflongestCommonSubstring(self,A,B):
# write your code here
lengthA = len(A)
lengthB = len(B)
iflengthA == lengthBandlengthA ==:
return
iflengthA ==orlengthB ==:
return
预设最大长度为A字符串长度,进行比较:
length = lengthA
whilelength >=1:
A字符串从位置0开始比较,起始位置+比较字符串长度不得超过A字符串最大长度,
如果在B字符串中能找到与A[startA:length+startA]相同的字符串,则返回length,否则A字符串中比较的位置向前进1,当length长度所有子串比较完没有找到B中符合的子串时,length -1,从A中开始位置重新比较。
直到length为1。
startA =
whilestartA + length
if notB.find(A[startA:length + startA]) == -1:
# print(length,A[startA:length+startA],B.find(A[startA:length+startA]))
returnlength
startA +=1
length -=1
运行结果:
代码:
领取专属 10元无门槛券
私享最新 技术干货