#2255

Easy

LeetCode Problem Workspace

Count Prefixes of a Given String

Count Prefixes of a Given String is a problem that involves finding the number of string prefixes in an array that match a given string.

array string

Problem Statement

You are given a list of words and a string s. Your task is to return the number of words in the list that are prefixes of the string s.

A prefix of a string is defined as a substring that starts at the beginning of the string and extends for any length. You must count how many of the strings in the list are prefixes of the given string s.

Examples

Example 1

Input: words = ["a","b","c","ab","bc","abc"], s = "abc"

Output: 3

The strings in words which are a prefix of s = "abc" are: "a", "ab", and "abc". Thus the number of strings in words which are a prefix of s is 3.

Example 2

Input: words = ["a","a"], s = "aa"

Output: 2

Both of the strings are a prefix of s. Note that the same string can occur multiple times in words, and it should be counted each time.

Constraints

1 <= words.length <= 1000
1 <= words[i].length, s.length <= 10
words[i] and s consist of lowercase English letters only.

Solution Approach

Iterating Through the List

One approach is to iterate through each word in the list and check if it is a prefix of the string s. This can be achieved using the startswith method in Python or similar string functions in other languages. If the word is a prefix, increment the counter.

Efficient Matching

To avoid unnecessary comparisons, stop as soon as you find a word that doesn’t match the prefix. This saves time and reduces redundant checks, making the algorithm more efficient.

Multiple Occurrences Handling

Remember to count all occurrences of a word in the list, even if it repeats. Each occurrence of a prefix should be considered separately.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the length of the input list and the length of the strings involved. A straightforward approach where each word is checked against the string s takes O(n * m) time, where n is the number of words and m is the maximum length of the words. The space complexity is O(1) if using an in-place comparison approach, as no extra space is needed aside from a few variables.

What Interviewers Usually Probe

The candidate is expected to demonstrate familiarity with string manipulation techniques.
Efficiency in handling edge cases such as duplicate words should be discussed.
Candidates may be expected to propose optimizations or alternative solutions for larger input sizes.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count duplicate words in the list.
Overcomplicating the solution by using complex algorithms for a simple problem.
Neglecting to account for edge cases such as an empty list or a word being exactly the same as s.

Follow-up variants

Instead of using the startswith method, implement a manual comparison of the beginning substring.
Consider a case where the list of words is very large, and explore optimized approaches like sorting or hashing.
Extend the problem to check for prefixes of multiple target strings, not just one.

FAQ

What is a prefix in the context of this problem?

A prefix is a substring that occurs at the beginning of the string. For example, 'abc' is a prefix of 'abcdef'.

How do I check if a word is a prefix of the given string?

You can use the built-in startswith method in Python, or compare the initial part of the string manually using slicing or iteration.

What if there are duplicate words in the list?

Each occurrence of a word, even if it repeats, should be counted as long as it is a prefix of the given string.

How can I optimize my solution for large inputs?

Consider using more efficient methods such as sorting or hashing to reduce unnecessary checks and speed up the process.

What is the expected time complexity for this problem?

The expected time complexity is O(n * m), where n is the number of words in the list and m is the maximum length of the words.

terminal

Solution

Solution 1: Traversal Counting

We directly traverse the array words, and for each string w, we check if s starts with w as a prefix. If it does, we increment the answer by one.

1

2

3

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        return sum(s.startswith(w) for w in words)

Continue Practicing

#2246 longest path with different adjacent characters #2273 find resultant array after removing anagrams #2227 encrypt and decrypt strings