題目敘述
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.
Constraints:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] consists of only lower-case English letters.
題目翻譯
要從字串陣列 strs 中找出這些元素最長的共同前綴，如果沒有就回傳空自串 ""。
解法解析
這題官方給了四種解法 Horizontal scanning、Vertical scanning、Divide and Conquer、Binary Search。
Horizontal scanning
這是從頭開始兩兩比較，找出最長的共同前綴。一路比較到結尾，如果有不同的字元，就直接返回前綴。
Vertical scanning
此方式則是每次比較一個字元，如果有不同的字元，就直接返回前綴。
Divide and Conquer
這是利用 Divide and Conquer 的方式，將原陣列分成兩半，然後再分別比較兩半的共同前綴。然後再比較兩半的共同前綴。
Binary Search
這是利用二分查找的方式，將原陣列分成兩半，然後再分別比較兩半的共同前綴。然後再比較兩半的共同前綴。與 Divide and Conquer 相同。
解法範例
Go
Horizontal scanning
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
for _, str := range strs[1:] {
for strings.Index(str, prefix) != 0 {
prefix = prefix[:len(prefix)-1]
if len(prefix) == 0 {
return ""
}
}
}
return prefix
}
Vertical scanning
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
for i := 0; i < len(strs[0]); i++ {
for _, str := range strs[1:] {
if i == len(str) || str[i] != strs[0][i] {
return strs[0][:i]
}
}
}
return strs[0]
}
Divide & conquer
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
return longestPrefix(strs, 0, len(strs)-1)
}
func longestPrefix(strs []string, start int, end int) string {
if start == end {
return strs[start]
}
mid := (start + end) / 2
left := longestPrefix(strs, start, mid)
right := longestPrefix(strs, mid+1, end)
return commonPrefix(left, right)
}
func commonPrefix(left string, right string) string {
var minLen int
if len(left) > len(right) {
minLen = len(right)
} else {
minLen = len(left)
}
for i := 0; i < minLen; i++ {
if left[i] != right[i] {
return left[:i]
}
}
return left[:minLen]
}
Binary Search
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
var low int = 1
var hight int = len(strs[0])
for i := 1; i < len(strs); i++ {
if len(strs[i]) < hight {
hight = len(strs[i])
}
}
for low <= hight {
mid := (low + hight) / 2
if isCommonPrefix(strs, mid) {
low = mid + 1
} else {
hight = mid - 1
}
}
return strs[0][:(low+hight)/2]
}
func isCommonPrefix(strs []string, length int) bool {
var str1 string = strs[0][:length]
for _, str := range strs[1:] {
if strings.Index(str, str1) != 0 {
return false
}
}
return true
}
JavaScript
Horizontal scanning
var longestCommonPrefix = function (strs) {
if (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 === "") return "";
}
}
return prefix;
};
Vertical scanning
var longestCommonPrefix = function (strs) {
if (strs.length === 0) return '';
for (let i = 0; i < strs[0].length; i++) {
for (const str of strs.slice(1, strs.length)) {
if (i === str.length || str[i] !== strs[0][i]) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
};
Divide & conquer
var longestCommonPrefix = function (strs) {
if (strs.length === 0) return '';
return longestPrefix(strs, 0, strs.length - 1);
};
const longestPrefix = (strs, start, end) => {
if (start === end) return strs[start];
const mid = Math.floor((start + end) / 2);
const left = longestPrefix(strs, start, mid);
const right = longestPrefix(strs, mid + 1, end);
return commonPrefix(left, right);
};
const commonPrefix = (left, right) => {
const minLength = Math.min(left.length, right.length);
for (let i = 0; i < minLength; i++) {
if (left[i] !== right[i]) {
return left.substring(0, i);
}
}
return left.substring(0, minLength);
};
Binary Search
var longestCommonPrefix = function (strs) {
if (strs.length === 0) return '';
let low = 1,
hight = Math.min(...strs.map((el) => el.length));
while (low <= hight) {
const mid = Math.floor((low + hight) / 2);
if (isCommonPrefix(strs, mid)) {
low = mid + 1;
} else {
hight = mid - 1;
}
}
return strs[0].substring(0, (low + hight) / 2);
};
const isCommonPrefix = (strs, len) => {
const str1 = strs[0].substring(0, len);
for (let i = 1; i < strs.length; i++) {
if (strs[i].indexOf(str1) !== 0) {
return false;
}
}
return true;
};
Kotlin
Horizontal scanning
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].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length - 1)
if (prefix.isEmpty()) return ""
}
}
return prefix
}
}
Vertical scanning
class Solution {
fun longestCommonPrefix(strs: Array<String>): String {
if (strs.isEmpty()) return ""
for (i in 0 until strs[0].length) {
for (j in 1 until strs.size) {
if (i == strs[j].length || strs[j][i] != strs[0][i]) {
return strs[0].substring(0, i)
}
}
}
return strs[0]
}
}
Divide & conquer
class Solution {
fun longestCommonPrefix(strs: Array<String>): String {
if (strs.isEmpty()) return ""
return longestPrefix(strs, 0, strs.size - 1)
}
fun longestPrefix(strs: Array<String>, l: Int, r: Int): String {
if (l == r) return strs[l]
val mid = (l + r) / 2
val lcpLeft = longestPrefix(strs, l, mid)
val lcpRight = longestPrefix(strs, mid + 1, r)
return commonPrefix(lcpLeft, lcpRight)
}
fun commonPrefix(left: String, right: String): String {
var minLen = Math.min(left.length, right.length)
for (i in 0 until minLen) {
if (left[i] != right[i]) {
return left.substring(0, i)
}
}
return left.substring(0, minLen)
}
}
Binary Search
class Solution {
fun longestCommonPrefix(strs: Array<String>): String {
if (strs.isEmpty()) return ""
var low = 1
var hight = strs[0].length
for (i in 1 until strs.size) {
hight = Math.min(hight, strs[i].length)
}
while (low <= hight) {
val mid = (low + hight) / 2
if (isCommonPrefix(strs, mid)) {
low = mid + 1
} else {
hight = mid - 1
}
}
return strs[0].substring(0, (low + hight) / 2)
}
private fun isCommonPrefix(strs: Array<String>, length: Int): Boolean {
var str1 = strs[0].substring(0, length)
for (i in 1 until strs.size) {
if (strs[i].substring(0, length) != str1) return false
}
return true
}
}
PHP
Horizontal scanning
class Solution
{
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 (strlen($prefix) === 0) {
return '';
}
}
}
return $prefix;
}
}
Vertical scanning
class Solution
{
function longestCommonPrefix($strs)
{
if (empty($strs) && is_null($strs)) {
return '';
}
for ($i = 0; $i < strlen($strs[0]); $i++) {
for ($j = 1; $j < count($strs); $j++) {
if ($i == strlen($strs[$j]) || $strs[0][$i] != $strs[$j][$i]) {
return substr($strs[0], 0, $i);
}
}
}
return $strs[0];
}
}
Divide & conquer
class Solution
{
function longestCommonPrefix($strs)
{
if (empty($strs) && is_null($strs)) {
return '';
}
return $this->longestPrefix($strs, 0, count($strs) - 1);
}
private function longestPrefix($strs, $l, $r)
{
if ($l == $r) {
return $strs[$l];
}
$mid = floor(($l + $r) / 2);
$lcpLeft = $this->longestPrefix($strs, $l, $mid);
$lcpRight = $this->longestPrefix($strs, $mid + 1, $r);
return $this->commonPrefix($lcpLeft, $lcpRight);
}
private function commonPrefix($left, $right)
{
$minLen = min(strlen($left), strlen($right));
for ($i = 0; $i < $minLen; $i++) {
if ($left[$i] != $right[$i]) {
return substr($left, 0, $i);
}
}
return substr($left, 0, $minLen);
}
}
Binary Search
class Solution
{
function longestCommonPrefix($strs)
{
if (empty($strs) && is_null($strs)) {
return '';
}
$low = 1;
$hight = max(array_map('strlen', $strs));
while ($low <= $hight) {
$mid = floor(($low + $hight) / 2);
if ($this->isCommonPrefix($strs, $mid)) {
$low = $mid + 1;
} else {
$hight = $mid - 1;
}
}
return substr($strs[0], 0, ($low + $hight) / 2);
}
function isCommonPrefix($strs, $length)
{
$str1 = substr($strs[0], 0, $length);
for ($i = 1; $i < count($strs); $i++) {
if (substr($strs[$i], 0, $length) != $str1) {
return false;
}
}
return true;
}
}
Python
Horizontal scanning
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0:
return ''
prefix = strs[0]
for string in strs[1:]:
while not string.startswith(prefix):
prefix = prefix[:-1]
if len(prefix) == 0:
return ''
return prefix
Vertical scanning
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0 and strs is None:
return ''
for i in range(len(strs[0])):
for string in strs[1:]:
if i == len(string) or string[i] != strs[0][i]:
return strs[0][:i]
return strs[0]
Divide & conquer
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if strs is None or len(strs) == 0:
return ''
return self.longestPrefix(strs, 0, len(strs) - 1)
def longestPrefix(self, strs: List[str], l: int, r: int) -> str:
if l == r:
return strs[l]
mid = (l + r) // 2
lcp_left = self.longestPrefix(strs, l, mid)
lcp_right = self.longestPrefix(strs, mid + 1, r)
return self.commonPrefix(lcp_left, lcp_right)
def commonPrefix(self, left: str, right: str) -> str:
min_len = min(len(left), len(right))
for i in range(min_len):
if left[i] != right[i]:
return left[:i]
return left[:min_len]
Binary Search
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if strs is None or len(strs) == 0:
return ''
low = 1
hight = len(min(strs, key=len))
while low <= hight:
middle = (low + hight) // 2
if self.isCommonPrefix(strs, middle):
low = middle + 1
else:
hight = middle - 1
return strs[0][:(low + hight) // 2]
def isCommonPrefix(self, strs: List[str], length: int) -> bool:
str1 = strs[0][:length]
for string in strs[1:]:
if not string.startswith(str1):
return False
return True
Rust
Swift
Horizontal scanning
class Solution {
func longestCommonPrefix(_ strs: [String]) -> String {
guard !strs.isEmpty else {
return ""
}
var prefix: String = strs.first!
for i: Int in 1..<strs.count {
while !strs[i].hasPrefix(prefix) {
prefix.removeLast()
guard !prefix.isEmpty else {
return ""
}
}
}
return prefix
}
}
Vertical scanning
class Solution {
func longestCommonPrefix(_ strs: [String]) -> String {
guard !strs.isEmpty else {
return ""
}
var prefix: String = ""
var iterators: [String.Iterator] = strs.map { $0.makeIterator() }
for letter: String.Element in strs[0] {
for j: Int in 1..<strs.count {
guard letter == iterators[j].next() else { return prefix }
}
prefix.append(letter)
}
return prefix
}
}
Divide & conquer
class Solution {
func longestCommonPrefix(_ strs: [String]) -> String {
guard !strs.isEmpty else {
return ""
}
return longestPrefix(strs, 0, strs.count - 1)
}
private func longestPrefix(_ strs: [String], _ l: Int, _ r: Int) -> String {
if l == r {
return strs[l]
}
let mid: Int = (l + r) / 2
let lcpLeft: String = longestPrefix(strs, l, mid)
let lcpRight: String = longestPrefix(strs, mid + 1, r)
return commonPrefix(lcpLeft, lcpRight)
}
private func commonPrefix(_ left: String, _ right: String) -> String {
var minLen: Int = min(left.count, right.count)
for i: Int in 0..<minLen {
if left[left.index(left.startIndex, offsetBy: i)] != right[right.index(right.startIndex, offsetBy: i)] {
return String(left[..<left.index(left.startIndex, offsetBy: i)])
}
}
return String(left[..<left.index(left.startIndex, offsetBy: minLen)])
}
}
Binary Search
class Solution {
func longestCommonPrefix(_ strs: [String]) -> String {
guard !strs.isEmpty else {
return ""
}
var minLen: Int = Int.max
for str: String in strs {
minLen = min(str.count, minLen)
}
var low: Int = 1
var hight: Int = minLen
while low <= hight {
let mid: Int = (low + hight) / 2
if isCommonPrefix(strs, mid) {
low = mid + 1
} else {
hight = mid - 1
}
}
let index: String.Index = strs[0].index(strs[0].startIndex, offsetBy: (low + hight)/2)
return String(strs[0][..<index])
}
private func isCommonPrefix(_ strs: [String], _ length: Int) -> Bool {
let str1: String = String(strs[0][..<(strs[0].index(strs[0].startIndex, offsetBy: length))])
for i: Int in 1..<strs.count {
if !strs[i].hasPrefix(str1) {
return false
}
}
return true
}
}