Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
//12ms
<?php
/**
* Created by PhpStorm.
* User: zhanglingyu
* Date: 2019-04-12
* Time: 12:32
*/
class Solution {
/**
* @param String[] $strs
* @return String
*/
function longestCommonPrefix($strs) {
if (count($strs) == 0) {
return "";
}
$maxStr = '';
$firstStr = array_shift($strs);
$len = strlen($firstStr);
for ($i=0; $i<$len; $i++) {
$flag = 1;
foreach ($strs as $s) {
$subStr = substr($s, 0 ,$i+1);
$temp = $maxStr . $firstStr[$i];
if ($subStr !== $temp) {
$flag = 0;
}
}
if (!$flag) {
return $maxStr;
} else {
$maxStr .= $firstStr[$i];
}
}
return $maxStr;
}
}
class Test extends \PHPUnit\Framework\TestCase
{
/** @test */
public function testSolution()
{
$solution = new Solution();
$arr = ["flower","flow","flight"];
$this->assertEquals($solution->longestCommonPrefix($arr), 'fl');
}
}
//20ms
/**
* @param String[] $strs
* @return String
*/
function longestCommonPrefix($strs) {
if (count($strs) == 0) {
return "";
}
if (count($strs) == 1) {
return $strs[0];
}
$res;
for ($i = 0; $i < count($strs) - 1; $i++) {
for ($wordLen = 0, $res = ""; $wordLen < (strlen($strs[$i]) < strlen($strs[$i + 1]) ? strlen($strs[$i]) : strlen($strs[$i + 1])); $wordLen++) {
if ($strs[$i][$wordLen] != $strs[$i + 1][$wordLen] && $wordLen == 0) {
break;
}
if ($strs[$i][$wordLen] == $strs[$i + 1][$wordLen]) {
$res .= $strs[$i][$wordLen];
}
}
$strs[$i + 1] = $res;
}
return $res;
}
// 0ms
func longestCommonPrefix(strs []string) string {
l := len(strs)
var res string
if l == 0 {
return res
}
// 只有一个元素
if l == 1 {
return strs[0]
}
firstStr := strs[0]
firstLen := len(firstStr)
var tmp string
for i:=0;i<firstLen ;i++ {
tmp = res + string( firstStr[i] )
flag := true
for j:=1;j<l ;j++ {
if i >= len(strs[j]) {
flag = false
break
}
substr := strs[j][0:i+1]
if substr != tmp{
flag = false
}
}
if !flag {
return res
} else {
res += string( firstStr[i] )
}
}
fmt.Println(firstLen)
return res
}
// 3ms
func longestCommonPrefix(strs []string) string {
var prefix string
if (len(strs) == 0) {
prefix = ""
} else {
prefix = strs[0]
for i := 1; i < len(strs); i++ {
for strings.HasPrefix(strs[i], prefix) == false {
prefix = string([]rune(prefix)[:len(prefix) - 1])
}
}
}
return prefix
}
//4ms 注意指定返回值
func longestCommonPrefix(strs []string) (result string) {
shortest := -1
for _, s := range strs {
if len(s) < shortest || shortest == -1{
shortest = len(s)
}
}
for i := 0; i < shortest; i++ {
for _, s := range strs {
if s[i] != strs[0][i] {
return
}
}
result += string(strs[0][i])
}
return
}
方法一一般是自己实现的方法，其他方式是在discuss中查找的更为优秀的方法，用作学习和借鉴。