Python实现-LeetCode（0014）-最长公共前缀（简

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:
  所有输入只包含小写字母 a-z 。

题解思路1（堆栈法）：
LeetCode中提交执行结果-执行用时：48 ms，内存消耗：13.6 MB。

from typing import List
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ''
        new_list = ['',strs[0]]
        for i in range(0,len(strs)):
            new_list[0] = ''
            new_list.append(strs[i])
            for j in range(min(len(new_list[1]),len(new_list[2]))):
                if new_list[1][j] == new_list[2][j]:
                    new_list[0] += new_list[1][j]
                else:
                    break
            new_list[1] = new_list[0]
            new_list.pop()
        return new_list[0]

print('“["flower","flow","flight"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["flower","flow","flight"])))
print('“["aca","cba"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["aca","cba"])))
print('“["a"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["a"])))
print('“["flower","flight","flow"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["flower","flight","flow"])))
print('“["dog","racecar","car"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["dog","racecar","car"])))
print('“[]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix([])))
print('“["acc","aaa","aaba"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["acc","aaa","aaba"])))

运行结果：

“["flower","flow","flight"]”中所有字符串的最长公共前缀为："fl"
“["aca","cba"]”中所有字符串的最长公共前缀为：""
“["a"]”中所有字符串的最长公共前缀为："a"
“["flower","flight","flow"]”中所有字符串的最长公共前缀为："fl"
“["dog","racecar","car"]”中所有字符串的最长公共前缀为：""
“[]”中所有字符串的最长公共前缀为：""
“["acc","aaa","aaba"]”中所有字符串的最长公共前缀为："a"

题解思路2（水平扫描法）：
LeetCode中提交执行结果-执行用时：48 ms，内存消耗：13.6 MB。
知识点：str.find()
a）描述：
原文：
S.find(sub[, start[, end]]) -> int
Return the lowest index in S where substring sub is found, such that sub is contained within S[start:end]. Optional arguments start and end are interpreted as in slice notation.
Return -1 on failure.

中文：
S.find(sub[, start[, end]]) -> int
返回S中找到子字符串sub的最低索引，该子字符串包含在S[start:end]中。可选参数的开始和结束被解释为切片符号。
失败返回-1。

诠释：
find() 方法检测字符串中是否包含子字符串 str ，如果指定 beg（开始） 和 end（结束） 范围，则检查是否包含在指定范围内，如果指定范围内如果包含指定索引值，返回的是索引值在字符串中的起始位置。如果不包含索引值，返回-1。

b）语法：
find()方法语法：str.find(str, beg=0, end=len(string))

c）参数：
str：指定检索的字符串；
beg：开始索引，默认为0；
end：结束索引，默认为字符串的长度。

d）返回值
如果包含子字符串返回开始的索引值，否则返回-1。

LeetCode中提交执行结果-执行用时：32 ms，内存消耗：13.6 MB。

from typing import List
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ''
        s = strs[0]
        for i in range(1, len(strs)):
            while strs[i].find(s) != 0:
                s = s[:-1]
        return s

print('“["flower","flow","flight"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["flower","flow","flight"])))
print('“["aca","cba"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["aca","cba"])))
print('“["a"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["a"])))
print('“["flower","flight","flow"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["flower","flight","flow"])))
print('“["dog","racecar","car"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["dog","racecar","car"])))
print('“[]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix([])))
print('“["acc","aaa","aaba"]”中所有字符串的最长公共前缀为："{}"'.format(Solution().longestCommonPrefix(["acc","aaa","aaba"])))

运行结果：

“["flower","flow","flight"]”中所有字符串的最长公共前缀为："fl"
“["aca","cba"]”中所有字符串的最长公共前缀为：""
“["a"]”中所有字符串的最长公共前缀为："a"
“["flower","flight","flow"]”中所有字符串的最长公共前缀为："fl"
“["dog","racecar","car"]”中所有字符串的最长公共前缀为：""
“[]”中所有字符串的最长公共前缀为：""
“["acc","aaa","aaba"]”中所有字符串的最长公共前缀为："a"