Quick Overview

This problem evaluates string-processing and filtering skills, focusing on exact prefix matching, case sensitivity, duplicate handling, and edge-case management over arrays of strings. Commonly asked in Coding & Algorithms interviews, it assesses practical implementation ability and understanding of algorithmic complexity at an implementation-level (basic to intermediate).

Return dictionary words matching a prefix

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of strings `words` (a dictionary) and a string `prefix`. Return all words in `words` that start with `prefix`. Clarifications/constraints: - Matching is case-sensitive. - If no words match, return an empty list. - If `words` contains duplicates, include duplicates in the output. - You may return the result in any order unless the interviewer asks for a specific ordering (e.g., lexicographic).

Quick Answer: This problem evaluates string-processing and filtering skills, focusing on exact prefix matching, case sensitivity, duplicate handling, and edge-case management over arrays of strings. Commonly asked in Coding & Algorithms interviews, it assesses practical implementation ability and understanding of algorithmic complexity at an implementation-level (basic to intermediate).

You are given a list of strings `words` representing a dictionary and a string `prefix`. Return all words in `words` that start with `prefix`. Rules: - Matching is case-sensitive. - If no words match, return an empty list. - If `words` contains duplicates, include duplicates in the output. - For this problem, return matching words in the same order they appear in `words`. - An empty prefix matches every word.

Constraints

  • 0 <= len(words) <= 100000
  • 0 <= len(prefix) <= 1000
  • Each element of `words` is a string
  • Matching must be case-sensitive

Examples

Input: (['apple', 'app', 'banana', 'apply'], 'app')

Expected Output: ['apple', 'app', 'apply']

Explanation: These are the words that start with 'app', kept in their original order.

Input: (['Cat', 'car', 'Cart', 'dog'], 'Ca')

Expected Output: ['Cat', 'Cart']

Explanation: Matching is case-sensitive, so 'car' does not match 'Ca'.

Hints

  1. Scan through the list once and decide for each word whether it begins with the prefix.
  2. Be careful with duplicates and with the case where `prefix` is an empty string.

Loading coding console...