DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Longest Common Prefix
FakeStandard
FakeStandard

Posted on

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

ζ‰Ύε‡Ίι™£εˆ—δΈ­ζ‰€ζœ‰ε…ƒη΄ ζœ€ι•·ηš„η›ΈεŒε­—η¬¦δΈ¦θΏ”ε›žοΌŒε¦‚ζžœζ²’ζœ‰η›ΈεŒε­—η¬¦ε‰‡θΏ”ε›žη©Ίε­—δΈ² ""。

例如 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;
}
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 ⭐
or buy me a coffee ⬇️ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)

Top Heroku Alternatives (For Free!)

Recently Heroku shut down free Heroku Dynos, free Heroku Postgres, and free Heroku Data for Redis on November 28th, 2022. So Meshv Patel put together some free alternatives in this classic DEV post.