题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。示例 1:
输入: ["flower","flow","flight"]
输出: "fl"示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。说明:
所有输入只包含小写字母 a-z 。
思考
看见这个题目，我能想到的最简单最好理解的，就是先把所有的可能的公共前缀找出来，然后去一个一个比较。这个所有的公共前缀其实很简单，第一个字符串的的前1个字符，前2个字符，以此类推直到最后。这里只需要简单的双循环就能解决问题。
看了官解的解法，我自己的这个解法有点类似官解的水平扫描法，从左到右扫描。
解题思路
- 把第一个字符串取出来，然后按照前1个字符，前2个字符，前3个字符，以此类推遍历一遍字符串，例如"flower"->["f","fl","flo","flow","flowe","flower"]
- 然后就是简单的把上面得到的字符串，跟得到的需要比较的字符串全部遍历一遍
- 如果找到了，那个字符串就是答案，没找到就返回空字符串
Python实现
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if 0 == len(strs): return "" #分解第一个字符串 checkStrList = list() for i in range(len(strs[0])): checkStrList.append(strs[0][0:(i + 1)]) #排除比较第一个字符串 targetStrs = strs[1:] resStr = "" for checkStr in checkStrList: bForceEnd = False for targetStr in targetStrs: if not targetStr.startswith(checkStr): bForceEnd = True break if bForceEnd: break resStr = checkStr return resStr执行用时 :48 ms, 在所有 Python3 提交中击败了85.61%的用户，内存消耗 :14 MB, 在所有 Python3 提交中击败了5.53%的用户
C++实现
class Solution {public: string longestCommonPrefix(vector<string>& strs) { if(0 == strs.size()) return ""; //分解第一个字符串 vector<string> checkStrs; for(auto i = 0; strs[0][i] != '\0'; ++i) { checkStrs.push_back(strs[0].substr(0, i + 1)); } string resStr = ""; for(auto i = 0; i < checkStrs.size(); ++i) { bool bForceEnd = false; for(auto j = 1; j < strs.size(); ++j)//排除比较第一个字符串 { std::size_t found = strs[j].find(checkStrs[i]); if(found == std::string::npos || found != 0) { bForceEnd = true; break; } } if(bForceEnd) { break; } resStr = checkStrs[i]; } return resStr; }};执行用时 :8 ms, 在所有 C++ 提交中击败了75.71%的用户，内存消耗 :9.1 MB, 在所有 C++ 提交中击败了72.94%的用户