Count Prefixes of a Given String — LeetCode 2255 Python Solution

The problem

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters. Return the number of strings in words that are a prefix of s.

Example

Input

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

Output

3

Explanation

The strings in words which are a prefix of s = "abc" are:

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2255. Count Prefixes of a Given String is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems