Longest Common Prefix

#algorithms #csharp #leetcode #easy

#14.Longest Common Prefix

Problem statement

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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Explanation

找出陣列中所有元素最長的相同字符並返回，如果沒有相同字符則返回空字串 ""。

例如 cat 和 carry 相同的前綴字符為 ca

Solution

用雙迴圈逐一比對，第一層遍歷元素長度，第二層則遍歷陣列內所有元素。

但是找尋陣列內元素時，不可使用超出元素長度的索引，故先找到陣列內最短長度的元素，再以此長度作為第一層迴圈的中止值。

public string LongestCommonPrefix(string[] strs)
{
    if (strs.Length == 0) return null;

    string res = string.Empty;
    string str = strs[0];

    foreach (var s in strs)
    {
        if (s.Length < str.Length)
            str = s;
    }

    int len = strs.Length;

    for (int i = 0; i < str.Length; i++)
    {
        for (int j = 0; j < len; j++)
        {
            if (str[i] == strs[j][i])
                continue;
            else
                return res;
        }

        res += str[i];
    }

    return res;
}

Reference

LeetCode Solution

GitHub Repository

Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐
or buy me a coffee ⬇️ I'd appreciate it.

Latest comments (0)

An Animated Guide to Node.js Event Loop

Node.js doesn’t stop from running other operations because of Libuv, a C++ library responsible for the event loop and asynchronously handling tasks such as network requests, DNS resolution, file system operations, data encryption, etc.

What happens under the hood when Node.js works on tasks such as database queries? We will explore it by following this piece of code step by step.