LeetCode 2255 - Count Prefixes of a Given String

LeetCode Problem 2255

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem asks us to determine how many strings in a given array words are prefixes of a target string s. A prefix of a string is defined as any substring that starts at the first character and continues for any length up to the length of the string itself. For example, "ab" is a prefix of "abc", but "bc" is not because it does not start at the first character. The input array words contains multiple candidate strings, and we must check each one against s.

The input constraints indicate that words can have up to 1000 strings, and each string, including s, can have up to 10 characters. This is relatively small, so algorithms with nested iterations over words and small string comparisons will run efficiently. It is important to note that strings in words can repeat, and each occurrence should be counted separately if it is a valid prefix. Edge cases include strings of length 1, duplicate entries, and cases where no strings match as prefixes.

Approaches

The brute-force approach is straightforward: iterate over each string in words and check if it is a prefix of s. This can be done using substring comparison. This approach is correct because it explicitly checks the definition of a prefix. Given the input constraints, this approach is actually efficient enough, but conceptually it involves checking each word individually, which is why it is considered brute force.

A slightly more optimized approach leverages the fact that strings in words are short (length <= 10). We can stop checking a word as soon as its length exceeds s, and we only need to compare the first len(word) characters of s. This reduces unnecessary comparisons and is conceptually cleaner, but in practice, the time complexity remains similar because of the small input sizes.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Check each word individually using substring comparison, where n = len(words), m = max length of word
Optimized	O(n * m)	O(1)	Stop checking words longer than s and only compare needed characters

Algorithm Walkthrough

1. Initialize a counter count to 0 to keep track of how many words are prefixes of s.
2. Iterate through each word in the words array.
3. For each word, first check if its length is less than or equal to the length of s. If it is longer, skip it because it cannot be a prefix.
4. Compare the word to the substring of s from index 0 to len(word). If they match, increment the counter count by 1.
5. Continue iterating until all words have been processed.
6. Return the value of count.

Why it works: This algorithm works because for each word, we directly check the necessary condition for being a prefix. The comparison only checks the characters that are relevant, ensuring correctness while avoiding unnecessary work for words that cannot possibly match.

Python Solution

from typing import List

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        count = 0
        for word in words:
            if len(word) <= len(s) and s[:len(word)] == word:
                count += 1
        return count

This implementation follows the algorithm closely. We initialize a counter, iterate through each word, and use slicing to compare the prefix directly. The length check ensures we do not attempt to slice beyond the string's bounds, preventing runtime errors.

Go Solution

func countPrefixes(words []string, s string) int {
    count := 0
    for _, word := range words {
        if len(word) <= len(s) && s[:len(word)] == word {
            count++
        }
    }
    return count
}

The Go solution mirrors the Python logic. Go slices strings similarly, and we compare substrings using ==. The length check ensures safe slicing. Unlike Python, Go requires explicit handling of slices and cannot use a dynamic type system, but the overall logic remains identical.

Worked Examples

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

Word	len(word) <= len(s)?	s[:len(word)]	Is Prefix?	count
"a"	yes	"a"	yes	1
"b"	yes	"a"	no	1
"c"	yes	"a"	no	1
"ab"	yes	"ab"	yes	2
"bc"	yes	"ab"	no	2
"abc"	yes	"abc"	yes	3

Final result: 3

Example 2: words = ["a","a"], s = "aa"

Word	len(word) <= len(s)?	s[:len(word)]	Is Prefix?	count
"a"	yes	"a"	yes	1
"a"	yes	"a"	yes	2

Final result: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m)	We iterate over n words and compare up to m characters for each word, where m <= 10
Space	O(1)	Only a counter variable is used; no additional data structures are needed

Given the constraints, this solution is efficient and runs well within the expected limits.

Test Cases

# provided examples
assert Solution().countPrefixes(["a","b","c","ab","bc","abc"], "abc") == 3  # multiple valid prefixes
assert Solution().countPrefixes(["a","a"], "aa") == 2  # duplicates counted

# edge cases
assert Solution().countPrefixes(["x"], "x") == 1  # single letter match
assert Solution().countPrefixes(["x"], "y") == 0  # single letter no match
assert Solution().countPrefixes(["abc", "abcd"], "abc") == 1  # longer word ignored
assert Solution().countPrefixes([], "abc") == 0  # empty words array
assert Solution().countPrefixes(["a","b","c"], "a") == 1  # only the first matches

Test	Why
["a","b","c","ab","bc","abc"], "abc"	Checks multiple matches and cumulative counting
["a","a"], "aa"	Tests duplicates being counted separately
["x"], "x"	Minimum length, exact match
["x"], "y"	Minimum length, no match
["abc", "abcd"], "abc"	Word longer than s should be ignored
[], "abc"	Empty input array
["a","b","c"], "a"	Only first word matches

Edge Cases

One edge case is when the words array is empty. The function must return 0 without attempting any substring comparisons, which our implementation handles naturally by iterating over an empty array.

Another edge case is when all words in words are longer than s. In this case, the length check prevents any out-of-bounds slicing and ensures no false matches are counted.

A third edge case is when words contains duplicates. Our algorithm correctly counts each occurrence separately, since each word is independently checked against s. This behavior is consistent with the problem statement and avoids undercounting.