LeetCode刷题-14-最长公共前缀

题目

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

示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。

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

思考

看见这个题目，我能想到的最简单最好理解的，就是先把所有的可能的公共前缀找出来，然后去一个一个比较。这个所有的公共前缀其实很简单，第一个字符串的的前 1 个字符，前 2 个字符，以此类推直到最后。这里只需要简单的 双循环 就能解决问题。

看了官解的解法，我自己的这个解法有点类似官解的水平扫描法，从左到右扫描。

解题思路

1. 把第一个字符串取出来，然后按照前 1 个字符，前 2 个字符，前 3 个字符，以此类推遍历一遍字符串，例如 ”flower”->[“f”,”fl”,”flo”,”flow”,”flowe”,”flower”]
2. 然后就是简单的把上面得到的字符串，跟得到的需要比较的字符串全部遍历一遍
3. 如果找到了，那个字符串就是答案，没找到就返回空字符串

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% 的用户