DEV Community

Cover image for Longest Common Prefix
FakeStandard
FakeStandard

Posted on • Edited on

2 1

Longest Common Prefix

#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"
Enter fullscreen mode Exit fullscreen mode

Example 2

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

Explanation

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

例如 catcarry 相同的前綴字符為 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;
}
Enter fullscreen mode Exit fullscreen mode

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 ⭐ I'd appreciate it.


Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay