We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Prefixes of a Given String

Number: 2341

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an array of strings (words) and a string s, count the number of strings in words that are prefixes of s. A prefix is a contiguous sequence of characters that starts at the beginning of s.

Key Insights

  • Iterate through each string in the words array.
  • For each string, check if it is a prefix of s.
  • Use the built-in string methods (like startsWith in JavaScript/Java, substr in C++ or slicing in Python) to perform the prefix check.
  • Each valid prefix should be counted even if duplicates exist.

Space and Time Complexity

Time Complexity: O(n * k), where n is the number of words and k is the average length of the words. Space Complexity: O(1) (ignoring the input space)

Solution

The solution involves iterating over the given array of words and checking for each if it is a prefix of string s. This is done using in-built string functions that compare the start of s with the word. Since the maximum length of the strings is small (up to 10), the direct approach works efficiently. The algorithm increments a counter for each word that is a prefix of s and returns the total count.

Code Solutions

# Define a function that counts the number of prefixes in words that are prefixes of s.
def countPrefixes(words, s):
    count = 0  # Counter for valid prefixes
    for word in words:
        # Check if the current word is a prefix of s using the startswith method
        if s.startswith(word):
            count += 1  # Increment the counter if it is a prefix
    return count

# Example usage:
words = ["a", "b", "c", "ab", "bc", "abc"]
s = "abc"
print(countPrefixes(words, s))  # Expected output: 3
← Back to All Questions