力扣00014.最长公共前缀

发表于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 5 分钟
最长公共前缀、字典树、字符串、简单

题目描述

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

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

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) {
            return "";
        }
        string prefix = strs[0];
        for (int i = 1; i < strs.size(); ++i) {
            while (strs[i].find(prefix) != 0) {
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) {
                    return "";
                }
            }
        }
        return prefix;
    }
};

结果

执行用时 : 4 ms, 击败 74.94% 使用 C++ 的用户

内存消耗 : 9.45 MB, 击败 36.89% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 40.09 MB, 击败 23.36% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        prefix = strs[0]
        for string in strs[1:]:
            while string.find(prefix) != 0:
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix

结果

执行用时 : 16 ms, 击败 86.01% 使用 Python 的用户

内存消耗 : 13.26 MB, 击败 17.29% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        prefix = ""
        min_length = min(len(s) for s in strs)
        for i in range(min_length):
            char = strs[0][i]
            if all(s[i] == char for s in strs):
                prefix += char
            else:
                break
        return prefix

结果

执行用时 : 44 ms, 击败 64.70% 使用 Python3 的用户

内存消耗 : 17.16 MB, 击败 5.01% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) {
        return "";
    }
    int i, j;
    for (i = 0; i < strlen(strs[0]); ++i) {
        for (j = 1; j < strsSize; ++j) {
            if (strs[j][i] != strs[0][i] || strs[j][i] == '\0') {
                char* result = (char*)malloc(sizeof(char) * (i + 1));
                strncpy(result, strs[0], i);
                result[i] = '\0';
                return result;
            }
        }
    }
    char* result = (char*)malloc(sizeof(char) * (i + 1));
    strncpy(result, strs[0], i);
    result[i] = '\0';
    return result;
}

结果

执行用时 : 4 ms, 击败 53.70% 使用 C 的用户

内存消耗 : 6.52 MB, 击败 47.21% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs == null || strs.Length == 0) {
            return "";
        }
        string prefix = strs[0];
        for (int i = 1; i < strs.Length; i++) {
            while (strs[i].IndexOf(prefix) != 0) {
                prefix = prefix.Substring(0, prefix.Length - 1);
                if (prefix.Length == 0) {
                    return "";
                }
            }
        }
        return prefix;
    }
}

结果

执行用时 : 72 ms, 击败 90.59% 使用 C# 的用户

内存消耗 : 42.74 MB, 击败 5.02% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) {
        return '';
    }
    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix.length === 0) {
                return '';
            }
        }
    }
    return prefix;
};

结果

执行用时 : 68 ms, 击败 55.60% 使用 JavaScript 的用户

内存消耗 : 47.75 MB, 击败 12.44% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function longestCommonPrefix(strs: string[]): string {
    if (strs === null || strs.length === 0) {
        return '';
    }
    let prefix: string = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix.length === 0) {
                return '';
            }
        }
    }
    return prefix;
}

结果

执行用时 : 56 ms, 击败 97.39% 使用 TypeScript 的用户

内存消耗 : 50.28 MB, 击败 8.64% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        if (empty($strs)) {
            return '';
        }
        $prefix = $strs[0];
        for ($i = 1; $i < count($strs); $i++) {
            while (strpos($strs[$i], $prefix) !== 0) {
                $prefix = substr($prefix, 0, strlen($prefix) - 1);
                if (empty($prefix)) {
                    return '';
                }
            }
        }
        return $prefix;
    }
}

结果

执行用时 : 8 ms, 击败 77.67% 使用 PHP 的用户

内存消耗 : 19.42 MB, 击败 5.82% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        guard !strs.isEmpty else { return "" }
        var prefix = strs[0]
        for i in 1..<strs.count {
            while !strs[i].hasPrefix(prefix) {
                prefix = String(prefix.dropLast())
                if prefix.isEmpty { return "" }
            }
        }
        return prefix
    }
}

结果

执行用时 : 8 ms, 击败 93.33% 使用 Swift 的用户

内存消耗 : 15.48 MB, 击败 14.08% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.isEmpty()) {
            return ""
        }
        var prefix = strs[0]
        for (i in 1 until strs.size) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.dropLast(1)
                if (prefix.isEmpty()) {
                    return ""
                }
            }
        }
        return prefix
    }
}

结果

执行用时 : 180 ms, 击败 51.52% 使用 Kotlin 的用户

内存消耗 : 36.44 MB, 击败 40.40% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
  String longestCommonPrefix(List<String> strs) {
    if (strs.isEmpty) {
      return '';
    }
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
      while (!strs[i].startsWith(prefix)) {
        prefix = prefix.substring(0, prefix.length - 1);
        if (prefix.isEmpty) {
          return '';
        }
      }
    }
    return prefix;
  }
}

结果

执行用时 : 284 ms, 击败 0.00% 使用 Dart 的用户

内存消耗 : 146.90 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    prefix := strs[0]
    for i := 1; i < len(strs); i++ {
        for !strings.HasPrefix(strs[i], prefix) {
            prefix = prefix[:len(prefix)-1]
            if prefix == "" {
                return ""
            }
        }
    }
    return prefix
}

结果

执行用时 : 4 ms, 击败 19.36% 使用 Go 的用户

内存消耗 : 2.21 MB, 击败 36.25% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
  return "" if strs.empty?
  prefix = strs[0]
  (1...strs.length).each do |i|
    while strs[i].index(prefix) != 0
      prefix = prefix.chop
      return "" if prefix.empty?
    end
  end
  prefix
end

结果

执行用时 : 48 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.80 MB, 击败 10.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
object Solution {
  def longestCommonPrefix(strs: Array[String]): String = {
    if (strs.isEmpty) {
      return ""
    }
    var prefix = strs(0)
    for (i <- 1 until strs.length) {
      while (!strs(i).startsWith(prefix)) {
        prefix = prefix.dropRight(1)
        if (prefix.isEmpty) {
          return ""
        }
      }
    }
    prefix
  }
}

结果

执行用时 : 488 ms, 击败 73.33% 使用 Scala 的用户

内存消耗 : 54.09 MB, 击败 86.67% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn longest_common_prefix(strs: Vec<String>) -> String {
        if strs.is_empty() {
            return String::new();
        }
        let mut prefix = strs[0].clone();
        for i in 1..strs.len() {
            while !strs[i].starts_with(&prefix) {
                prefix.pop();
                if prefix.is_empty() {
                    return String::new();
                }
            }
        }
        prefix
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.12 MB, 击败 35.11% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户