# LeetCode Solution, Easy, 14. Longest Common Prefix

# [14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)

## 題目敘述

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 <= 200`
- `0 <= strs[i].length <= 200`
- `strs[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

```go
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

```go
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

```go
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

```go
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

```javascript
/**
 * @param {string[]} strs
 * @return {string}
 */
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

```javascript
/**
 * @param {string[]} strs
 * @return {string}
 */
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

```javascript
/**
 * @param {string[]} strs
 * @return {string}
 */
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

```javascript
/**
 * @param {string[]} strs
 * @return {string}
 */
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

```kotlin
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

```kotlin
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

```kotlin
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

```kotlin
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

```php
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 (strlen($prefix) === 0) {
                    return '';
                }
            }
        }
        return $prefix;
    }
}
```

##### Vertical scanning

```php
class Solution
{

    /**
     * @param String[] $strs
     * @return String
     */
    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

```php
class Solution
{

    /**
     * @param String[] $strs
     * @return String
     */
    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

```php
class Solution
{

    /**
     * @param String[] $strs
     * @return String
     */
    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

```python
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

```python
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

```python
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

```python
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

```rust
```

#### Swift

##### Horizontal scanning

```swift
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

```swift
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

```swift
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

```swift
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
    }
}
```