阶梯训练1-字符串处理

出门了几天,没机会摸电脑...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

运行结果:

代码:

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180311G0BXDJ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券