Skip to content

14. Longest Common Prefix

Array String Trie

Problem - Longest Common Prefix

Easy

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.

 

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters if it is non-empty.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        string firstStr = strs[0];

        for (int i = 0; i < firstStr.Length; i++) {
            char c = firstStr[i];
            for (int j = 1; j < strs.Length; j++) {
                if (i >= strs[j].Length || strs[j][i] != c) {
                    return firstStr.Substring(0, i);
                }
            }
        }

        return firstStr;
    }
}

Submission Stats:

  • Runtime: 67 ms (5.15%)
  • Memory: 42 MB (100.00%)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        prefix = strs[0]
        for word in strs[1:]:
            while not word.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.8 MB (78.62%)