Jobs

Interviews

Discussions

Count Prefixes of a Given String

Easy

Asked by:

20 views

Topics:

ArraysStrings

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.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Example 1:

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:
"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
Explanation:
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.

Try coding it in LeetCode

Count Prefixes of a Given String

Easy

Asked by:

20 views

Topics:

ArraysStrings

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.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Example 1:

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:
"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
Explanation:
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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `words` array be empty, or can the `s` string be empty? What should be returned in those cases?
Are the strings in the `words` array and the string `s` case-sensitive?
Are there any constraints on the length of the strings in the `words` array, or on the length of the string `s`? What is the maximum possible length?
Can the `words` array contain duplicate strings?
By prefix, do you mean a substring that starts at the beginning of the string `s`?

Brute Force Solution

Approach

We want to find out how many words from a list are prefixes of a given target word. The brute force method involves checking each word in the list to see if it appears at the very beginning of the target word by comparing characters one by one.

Here's how the algorithm would work step-by-step:

Take the first word from the list of words.
Compare it, character by character, with the beginning of the target word.
If all the characters of the word match the beginning of the target word in the correct order, then it's a prefix. If any character doesn't match, it's not a prefix.
Count how many prefixes have been found so far.
Repeat the process, using the next word on the list to compare to the target word.
Continue this process until every word on the list has been checked.
The final count is the total number of prefixes from the word list that matched the target word.

Code Implementation

def count_prefixes_brute_force(words, target_word):    prefix_count = 0

    for current_word in words:
        is_prefix = True
        # If current word is longer than
        # the target, it cannot be a prefix
        if len(current_word) > len(target_word):
            continue

        # Iterate through each char to compare
        for char_index in range(len(current_word)):
            if current_word[char_index] != target_word[char_index]:
                is_prefix = False
                break
        # Increment count when matching prefix
        if is_prefix:
            prefix_count += 1

    return prefix_count

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of words in the input list and m be the maximum length of a word in the list or the target string. For each of the n words in the input list, we perform a character-by-character comparison with the target string. In the worst case, we compare all characters of the current word with the beginning of the target string which would be m operations. Therefore, in the worst case, we perform m operations n times leading to O(n*m) time complexity.

Space Complexity

O(1) – The provided algorithm iterates through the list of words and compares each word to the target word character by character. It uses a counter to keep track of the number of prefixes found. The algorithm doesn't create any auxiliary data structures whose size depends on the input (the list of words or the target word). Only a few constant-size variables are used for indexing and counting, regardless of the input size. Therefore, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to count prefixes is to build a special data structure that allows for quick prefix lookups. We'll create something like a tree where each branch represents a character, and then use this tree to see how many prefixes of the given string are present in a list of words.

Here's how the algorithm would work step-by-step:

First, organize all the words into a structure resembling a tree. Start with an empty root.
For each word, add it to the tree character by character, creating new branches as needed. Mark the end of each word as a 'complete word'.
Now, take the given string. Traverse the tree, character by character, matching each character from the string.
Every time you reach a 'complete word' along the way, increase the count of prefixes.
Continue traversing the tree until you've used all the characters of the string, or you can no longer find a matching character in the tree.
The final count is the number of prefixes of the given string that were found in the list of words.

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                current_node.children[char] = TrieNode()
            current_node = current_node.children[char]
        current_node.is_end_of_word = True

def count_prefixes(list_of_words, search_string):
    trie = Trie()
    for word in list_of_words:
        trie.insert(word)

    current_node = trie.root
    prefix_count = 0

    for char in search_string:
        if char in current_node.children:
            current_node = current_node.children[char]

            # Count if the current node marks the end of a word
            if current_node.is_end_of_word:
                prefix_count += 1

        else:
            # Stop if no matching character is found
            break

    return prefix_count

Big(O) Analysis

Time Complexity

O(N*M) – Let N be the length of the input list of words and M be the length of the given string. Building the Trie involves iterating through each word in the list, which takes O(L) time for each word where L is the average length of the word. We will perform this on N words. Traversal will take O(M), where M is the length of the string as we need to iterate over each character of the string once. In the worst case, building the Trie involves iterating over each character of all words, taking O(N*L) and traversal involves visiting M nodes. So the complexity is O(N*L + M), which simplifies to O(N*M) when we assume L and M are comparable.

Space Complexity

O(M*L) – The primary space complexity comes from building the tree-like structure, also known as a Trie, to store all the words. In the worst-case scenario, where no words share prefixes, each word will add a new branch for each of its characters. If we have M words, and the longest word has length L, the Trie could potentially store M*L nodes. Therefore, the auxiliary space used is proportional to the total number of characters across all the words, resulting in a space complexity of O(M*L).

Edge Cases

Case	How to Handle
Null input string	Throw IllegalArgumentException or return 0 to signal invalid input.
Null input prefixes array	Throw IllegalArgumentException or return 0 to signal invalid input.
Empty input string	Return the count of empty strings in the prefixes array.
Empty prefixes array	Return 0 since there are no prefixes to count.
Prefixes array contains null or empty strings	Handle null prefixes by skipping them or throwing an exception; count empty prefixes if the input string is empty or a prefix itself.
Very long input string and prefixes array (scalability)	Ensure the solution uses efficient string comparison (e.g., startsWith or similar optimized method) to avoid quadratic time complexity.
Prefixes array contains duplicates	The solution should count each duplicate prefix if it appears multiple times and is a prefix of the input string.
Input string is a prefix of other strings in the prefixes array	The solution should correctly identify when the whole input string is present as a prefix and count accordingly.

Null input string

How to Handle:

Throw IllegalArgumentException or return 0 to signal invalid input.

Null input prefixes array

How to Handle:

Throw IllegalArgumentException or return 0 to signal invalid input.

Empty input string

How to Handle:

Return the count of empty strings in the prefixes array.

Empty prefixes array

How to Handle:

Return 0 since there are no prefixes to count.

Prefixes array contains null or empty strings

How to Handle:

Handle null prefixes by skipping them or throwing an exception; count empty prefixes if the input string is empty or a prefix itself.

Very long input string and prefixes array (scalability)

How to Handle:

Ensure the solution uses efficient string comparison (e.g., startsWith or similar optimized method) to avoid quadratic time complexity.

Prefixes array contains duplicates

How to Handle:

The solution should count each duplicate prefix if it appears multiple times and is a prefix of the input string.

Input string is a prefix of other strings in the prefixes array

How to Handle:

The solution should correctly identify when the whole input string is present as a prefix and count accordingly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `words` array be empty, or can the `s` string be empty? What should be returned in those cases?
Are the strings in the `words` array and the string `s` case-sensitive?
Are there any constraints on the length of the strings in the `words` array, or on the length of the string `s`? What is the maximum possible length?
Can the `words` array contain duplicate strings?
By prefix, do you mean a substring that starts at the beginning of the string `s`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first word from the list of words.
Compare it, character by character, with the beginning of the target word.
If all the characters of the word match the beginning of the target word in the correct order, then it's a prefix. If any character doesn't match, it's not a prefix.
Count how many prefixes have been found so far.
Repeat the process, using the next word on the list to compare to the target word.
Continue this process until every word on the list has been checked.
The final count is the total number of prefixes from the word list that matched the target word.

Code Implementation

def count_prefixes_brute_force(words, target_word):    prefix_count = 0

    for current_word in words:
        is_prefix = True
        # If current word is longer than
        # the target, it cannot be a prefix
        if len(current_word) > len(target_word):
            continue

        # Iterate through each char to compare
        for char_index in range(len(current_word)):
            if current_word[char_index] != target_word[char_index]:
                is_prefix = False
                break
        # Increment count when matching prefix
        if is_prefix:
            prefix_count += 1

    return prefix_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, organize all the words into a structure resembling a tree. Start with an empty root.
For each word, add it to the tree character by character, creating new branches as needed. Mark the end of each word as a 'complete word'.
Now, take the given string. Traverse the tree, character by character, matching each character from the string.
Every time you reach a 'complete word' along the way, increase the count of prefixes.
Continue traversing the tree until you've used all the characters of the string, or you can no longer find a matching character in the tree.
The final count is the number of prefixes of the given string that were found in the list of words.

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                current_node.children[char] = TrieNode()
            current_node = current_node.children[char]
        current_node.is_end_of_word = True

def count_prefixes(list_of_words, search_string):
    trie = Trie()
    for word in list_of_words:
        trie.insert(word)

    current_node = trie.root
    prefix_count = 0

    for char in search_string:
        if char in current_node.children:
            current_node = current_node.children[char]

            # Count if the current node marks the end of a word
            if current_node.is_end_of_word:
                prefix_count += 1

        else:
            # Stop if no matching character is found
            break

    return prefix_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input string	Throw IllegalArgumentException or return 0 to signal invalid input.
Null input prefixes array	Throw IllegalArgumentException or return 0 to signal invalid input.
Empty input string	Return the count of empty strings in the prefixes array.
Empty prefixes array	Return 0 since there are no prefixes to count.
Prefixes array contains null or empty strings	Handle null prefixes by skipping them or throwing an exception; count empty prefixes if the input string is empty or a prefix itself.
Very long input string and prefixes array (scalability)	Ensure the solution uses efficient string comparison (e.g., startsWith or similar optimized method) to avoid quadratic time complexity.
Prefixes array contains duplicates	The solution should count each duplicate prefix if it appears multiple times and is a prefix of the input string.
Input string is a prefix of other strings in the prefixes array	The solution should correctly identify when the whole input string is present as a prefix and count accordingly.

Null input string

How to Handle:

Throw IllegalArgumentException or return 0 to signal invalid input.

Null input prefixes array

How to Handle:

Throw IllegalArgumentException or return 0 to signal invalid input.

Empty input string

How to Handle:

Return the count of empty strings in the prefixes array.

Empty prefixes array

How to Handle:

Return 0 since there are no prefixes to count.

Prefixes array contains null or empty strings

How to Handle:

Handle null prefixes by skipping them or throwing an exception; count empty prefixes if the input string is empty or a prefix itself.

Very long input string and prefixes array (scalability)

How to Handle:

Ensure the solution uses efficient string comparison (e.g., startsWith or similar optimized method) to avoid quadratic time complexity.

Prefixes array contains duplicates

How to Handle:

The solution should count each duplicate prefix if it appears multiple times and is a prefix of the input string.

Input string is a prefix of other strings in the prefixes array

How to Handle:

The solution should correctly identify when the whole input string is present as a prefix and count accordingly.