C# - 6 lines - O(n * len of prefix) - most optimal I can think of.


  • 0

    I'm sure there is a more clever way, but this seems like the most optimal I can think of

    • start at index 0
    • check each string if they have the same char at the index
    • if all have the same char increment the index
    • terminate if any mismatch is found or any string has exceeded it's length
    • also, avoids any string functions, adding strings, sub string, etc (except in my return)

    This seems like it will terminate the quickest, as soon as any string runs out or any character is not a match. It will do no unnecessary compares.

        public string LongestCommonPrefix(string[] strs) 
        {
            int min = 0;
            while (strs.Length > 0)
            {
                foreach (string s in strs)
                {
                    if (s.Length == min || s[min] != strs[0][min]) return strs[0].Substring(0, min);
                }
                min++;
            }
            return "";
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.