014 longest common prefix
14. Longest Common Prefix
题目: https://leetcode.com/problems/longest-common-prefix/
难度:
Easy
思路：
解法1:
以一个小例子来解释，strs=['laa', 'lab', 'lac'], 如果存在LCP的话它肯定就在第一个字符串strs[0]中，并且LCP的长度肯定不会大于strs[0]的长度 - 依次假设LCP长度为0到len(strs[0]),在每一轮循环中: - 1. 只要strs中存在比当前长度i更短的string，立刻返回上一轮LCP，即strs[0][:i] 2. 只要strs中存在当前index字符与LCP该index不相同的字符串，立刻返回上一轮LCP，即strs[0][:i] - 如果一直没返回，说明strs[0]本身就是LCP，返回它
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
for i in range(len(strs[0])):
for str in strs:
if len(str) <= i or strs[0][i] != str[i]:
return strs[0][:i]
return strs[0]
解法2:
- dp[i]代表前i+1个字符串的最大前缀串，
- 如果第i+2个字符串不以dp[i]为前缀，就去掉dp[i]的最后一个字符再试一次
- 都去完了那么dp[i+1]肯定就是空串了，也就等于这时候的dp[i]，因为dp[i]的每个字符已经被去完了
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ''
dp = [strs[0]]*len(strs)
for i in range(1,len(strs)):
while not strs[i].startswith(dp[i-1]):
dp[i-1] = dp[i-1][:-1]
dp[i] = dp[i-1]
return dp[-1]
python无敌啊！！！有没有天理啊，手动滑稽😏😏😏😏！一行解法：
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
return os.path.commonprefix(strs)
