# 14. 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.

## 解法解析

### 解法範例

#### 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]
}
``````
``````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
``````/**
* @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
``````/**
* @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
``````/**
* @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);
};
``````
``````/**
* @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
``````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)
}
}
``````
``````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
{

/**
* @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
``````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
``````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);
}
}
``````
``````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
``````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]
``````
``````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)])
}
}
``````
``````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
}
}
``````