Skip to main content
Hashnode不工程的攻城獅

Command Palette

Search for a command to run...

LeetCode Solution, Easy, 14. Longest Common Prefix

找出最長的共同前綴

Published
攻
攻城獅

I am not a programmer just a leaner. Writing JavaScript, Python, and Go and doing something on Kubernetes.

Part of seriesLeetCode Solution

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
    }
}
#leetcode#learning#learn-coding#programming#programming-blogs

Comments

Join the discussion

No comments yet. Be the first to comment.

LeetCode Solution

Part 1 of 50

A collection of leetcode solustion

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

現在應該開始有很多人想要踏入軟體工程的領域，但在進入這個領域之前，覺得先了解一些名詞，可以在入門時更有方向也更知道要用什麼關鍵字去找尋有用的資訊。這篇文章就是想要幫助想要入門的人理解一些軟體工程裡的專有名詞。 作業系統 這一區塊主要解釋跟作業系統層面相關的名詞 英文中文解釋 Operation system 簡稱 OS | 作業系統 | 就是電腦的作業系統，是三大作業系統分別是：Linux、Windows、macOS | | Linux | | 自由和開放原始碼的 UNI...

May 10, 2023

我的 MacBook Pro (Apple Silicon) 設定

現在開始因為 ChatGPT 的出現，各種 AI 助手的功能都跑出來了。想想自己用了許久的環境設定也應該要來重新審視和建立新的開發環境了，僅此紀錄我個人的環境配置步驟和設定。 環境前置步驟 還原 MacBook Pro 至全新環境 macOS（全部資料刪除） 設定好初始設定後，登入 Apple ID 進入 App Store 確定 macOS 版本和預設 APP 都更新到最新 macOS 版本 到系統設定調整所有設定至個人習慣的設定 三指拖移 觸控板手勢開啟 防火牆開啟 輸入法設定...

Apr 25, 2023

ChatGPT 下的發展預想

從 ChatGPT 問世到現在，有許許多多的文章和討論出來。先從最早的 Google 要完蛋了，到後來的工作要被取代了，工程師失業了。 我就比較沒有想要馬上出來評論一下，我喜歡讓子彈飛一會兒。跟討論一下我自己比較在意的討論點。 Google 為什麼慢了? 結論：因為他需要更小心 很多人說 Google 怎麼被微軟搶先了一步。剛開始 Bing 說要加上 AI 的時候大家都在說 Google 怎麼慢了。我就馬上跑去看 OpenAI 的網站，靠北呀啊就 Azure 贊助的。那當然在正式上線 ChatG...

Mar 23, 2023
不

不工程的攻城獅

223 posts

I am not a programmer because I am not good at programming. But I do programming. Love to learn new things. An animal lover and a dancer. My oshi is 潤羽るしあ.