Katkat
Back

Find Common Prefix Across Strings

AppleSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to manipulate strings and iterate through arrays to find the longest common prefix among a list of words, emphasizing efficiency and edge-case handling.

Problem Statement

Write a function longestCommonPrefix(strs: List[str]) -> str that finds the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

Constraints

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters.

Examples

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.

Edge Cases to Consider

  • An empty input list.
  • A list containing a single string.
  • A list where one of the strings is an empty string.
  • A list where all strings are identical.

Hints

Hint 1

Consider picking the first string as an initial reference and comparing it against each subsequent string character by character.

Hint 2

If you encounter a mismatch while comparing, the current prefix must be truncated to the length where the mismatch occurred.

Hint 3

Alternatively, sort the array of strings and compare only the first and last strings, as they will be the most different lexicographically.

Follow-up questions

  • What is the time and space complexity of your solution, and can it be optimized further?
  • How would you modify your approach if you had to find the longest common suffix instead of a prefix?
  • If the input array were massive and stored on disk, how would your approach change to minimize I/O operations?