Katkat
Back

Find First Prefix-Matching Word

PinterestSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently search through a collection of strings to find the first element that satisfies a specific prefix condition, emphasizing clean iteration and edge case management.

Problem Statement

Given an array of strings words and a target string prefix, write a function that returns the first string in the array that starts with the given prefix. If no such string exists, return an empty string.

Function Signature

def find_first_prefix(words: list[str], prefix: str) -> str:

Constraints

  • 0 <= len(words) <= 10,000
  • 0 <= len(prefix) <= 100
  • All strings consist of lowercase English letters.

Examples

Example 1:

  • Input: words = ["apple", "appetizer", "apply", "banana"], prefix = "app"
  • Output: "apple"
  • Explanation: "apple" is the first word that starts with "app".

Example 2:

  • Input: words = ["cat", "dog", "bird"], prefix = "z"
  • Output: ""
  • Explanation: None of the words start with "z".

Edge Cases

  • The words list is empty.
  • The prefix is an empty string (an empty string is a prefix of any string).
  • No word matches the prefix.

Hints

Hint 1

Consider the built-in string methods available in your programming language that check for prefixes.

Hint 2

A simple linear scan from the beginning of the list to the end is sufficient to ensure you find the first match.

Hint 3

If the prefix is an empty string, what should the function return based on the requirement that the first word is the match?

Follow-up questions

  • How would you optimize this search if the `words` array was massive and you needed to perform thousands of prefix queries?
  • How does the time complexity change if you preprocess the input using a Trie data structure?
  • What if the input `words` array was sorted? Could you use binary search to achieve better than O(N) time complexity?