Not a programmer 不工程的攻城獅

LeetCode Solution, Easy, 14. Longest Common Prefix

找出最長的共同前綴

攻城獅's photo
攻城獅

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.

題目翻譯

要從字串陣列 strs 中找出這些元素最長的共同前綴，如果沒有就回傳空自串 ""。

解法解析

這題官方給了四種解法 Horizontal scanning、Vertical scanning、Divide and Conquer、Binary Search。

Horizontal scanning

這是從頭開始兩兩比較，找出最長的共同前綴。一路比較到結尾，如果有不同的字元，就直接返回前綴。

Vertical scanning

此方式則是每次比較一個字元，如果有不同的字元，就直接返回前綴。

Divide and Conquer

這是利用 Divide and Conquer 的方式，將原陣列分成兩半，然後再分別比較兩半的共同前綴。然後再比較兩半的共同前綴。

這是利用二分查找的方式，將原陣列分成兩半，然後再分別比較兩半的共同前綴。然後再比較兩半的共同前綴。與 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]
}

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

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

leetcodelearninglearn codingGeneral ProgrammingProgramming Blogs