LeetCode–最长公共前缀

LeetCode–最长公共前缀

博客说明

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！

说明

leetcode题，14题

最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

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

示例 2:

输入: ["dog","racecar","car"] 输出: ""

解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z

Java

水平扫描法

依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。

class Solution { public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0){ return ""; } //假设第一个字段为公共前缀 String prefix = strs[0]; int count = strs.length; for(int i = 1;i<count;i++){ //获取两个字符串最长前缀 prefix = longestCommonPrefix(prefix,strs[i]); if(prefix.length() == 0){ break; } } return prefix; } //获取两个字符串最长前缀 public String longestCommonPrefix(String str1,String str2){ int length = Math.min(str1.length(),str2.length()); int index = 0; while(index<length && str1.charAt(index) == str2.charAt(index)){ index++; } return str1.substring(0,index); } }

Python

水平扫描法

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" #假设第一个字段为公共前缀 prefix , count = strs[0],len(strs) for i in range(1,count): #获取两个字符串最长前缀 prefix = self.commonPrefix(prefix,strs[i]) if not prefix: return "" return prefix #获取两个字符串最长前缀 def commonPrefix(self,str1,str2): length,index = min(len(str1),len(str2)),0 while index < length and str1[index] == str2[index]: index += 1 return str1[:index]

C++

水平扫描法

class Solution { public: string longestCommonPrefix(vector<string>& strs) { if(!strs.size()){ return ""; } string prefix = strs[0]; int count = strs.size(); for (int i = 1;i < count; i++){ prefix = longestCommonPrefix(prefix,strs[i]); if (!prefix.size()){ break; } } return prefix; } string longestCommonPrefix(const string& str1,const string& str2){ int index = 0; int length = min(str1.size(),str2.size()); while(index < length && str1[index] == str2[index]){ index++; } return str1.substr(0,index); } };

PHP

水平扫描法

class Solution { /** * @param String[] $strs * @return String */ function longestCommonPrefix($strs) { $prefix = ''; $i = 0; //判断其中是否有字符串长度为0 foreach($strs as $key => $value){ if($value == ''){ return $prefix; } } //判断个数是否为空 if(count($strs)<1){ return $prefix; } while(true){ //获取当前第i个字符 $current = $strs[0]{$i}; if(!$current){ return $prefix; } foreach($strs as $key => $value){ if($value{$i} != $current){ return $prefix; } } $prefix .= $current; $i++; } return $prefix; } }

感谢

leetcode

以及勤劳的自己