每日一题——最长公共前缀

题目描述

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

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

示例

1
2
3
4
5
6
输入: ["flower","flow","flight"]
输出: "fl"

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

说明:

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

思路

  • 因为要找最长 “公共” 前缀，那么意味着我们可以任一一个元素找到
  • 通过任一元素建立 “基准” 元素，不断更新比较，即可正确求解
  • 最后处理下边界条件即可

代码

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @param String[] $strs
* @return String
*/
function longestCommonPrefix($strs) {
    foreach ($strs as $ke=>$value) {
        if ($value == '') {
            return '';
        }
    }
    if (count($strs)==1){
        return $strs[0];
    }        
    $len = strlen($strs[0]);
    $i = 0;
    while ($i<=$len) {
        $str =  substr($strs[0],$i,1);
        for ($j = 1; $j < count($strs); $j++) {
            if ($str != substr($strs[$j],$i,1) or $i==$len) {                    
                return substr($strs[0],0,$i);
            }
        }
        $i++;
    }
    return '';
}

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func longestCommonPrefix(strs []string) string {
    if len(strs) < 1 {
        return ""
    }
    prefix := strs[0]
    for _,str := range strs {
        for strings.Index(str,prefix) != 0 {	// ?作用
            if len(prefix) == 0 {
                return ""
            }
            prefix = prefix[:len(prefix) - 1]
        }
    }
    return prefix
}