Jobs

Interviews

Discussions

Check If String Is a Prefix of Array

Easy

Uber

1 view

Topics:

ArraysStrings

Given a string s and an array of strings words, determine whether s is a prefix string of words.

A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.

Return true if s is a prefix string of words, or false otherwise.

Example 1:

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]
Output: true
Explanation:
s can be made by concatenating "i", "love", and "leetcode" together.

Example 2:

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]
Output: false
Explanation:
It is impossible to make s using a prefix of arr.

Constraints:

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

Check If String Is a Prefix of Array

Easy

Uber

1 view

Topics:

ArraysStrings

Given a string s and an array of strings words, determine whether s is a prefix string of words.

A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.

Return true if s is a prefix string of words, or false otherwise.

Example 1:

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]
Output: true
Explanation:
s can be made by concatenating "i", "love", and "leetcode" together.

Example 2:

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]
Output: false
Explanation:
It is impossible to make s using a prefix of arr.

Constraints:

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

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 input string or any of the strings in the array be empty or null?
Are the strings in the input array guaranteed to be composed of only alphanumeric characters, or can they contain special characters or spaces?
If the string is not a prefix of the array, what should I return? Should I return false or throw an exception?
Can the same string from the array be used multiple times to form the prefix?
What are the size constraints for the input string and the strings within the array?

Brute Force Solution

Approach

The goal is to see if a given long word can be formed by sticking together the beginning words from a collection of smaller words. We'll try all possible combinations of starting words to see if any match the long word exactly.

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

Begin by considering just the first word from the collection of smaller words.
Check if this first word is identical to the long word. If so, we have a match!
If not, consider the first two words stuck together and check if that matches the long word.
Keep adding words, one at a time, from the collection to the growing combined word, and comparing this combined word to the long word after each addition.
If at any point the combined word becomes longer than the long word, we know it's not a prefix, and we can stop checking that particular combination.
Continue this process until we either find a match (the combined word is identical to the long word) or we have used all the words in the collection and still haven't found a match.

Code Implementation

def is_prefix_of_array(long_word, array_of_words):
    combined_word = ""

    for word in array_of_words:
        combined_word += word

        # Check if the combined word matches the long word
        if combined_word == long_word:
            return True

        # If the combined word is longer, it can't be a prefix
        if len(combined_word) > len(long_word):
            return False

    # If we get here, no prefix was found
    return False

Big(O) Analysis

Time Complexity

O(m) – The algorithm iterates through the input array of words once, concatenating them until the combined length equals or exceeds the length of the target string 's'. In the worst case, it concatenates a significant portion of the words array to reach the target string's length. The dominating factor is the string concatenation and comparison, with each operation contributing a cost proportional to the length 'm' of the target string 's'. Therefore the time complexity is O(m), where m is the length of the string s.

Space Complexity

O(1) – The algorithm constructs a combined word string incrementally. While the length of this combined word can grow up to the length of the input string 's', this string can be thought of as overwriting the input string. In terms of auxiliary space, beyond the inputs themselves, we are creating a temporary string and a few index variables. The temporary string to store the combined word has a space complexity proportional to the length of the `s`, however, since `s` is technically part of the input, the temporary combined string is not considered auxiliary. Thus, only a constant amount of extra space for index variables is used, resulting in O(1) space complexity.

Optimal Solution

Approach

We want to see if our target string can be formed by combining the beginning elements of a given list of words. The efficient way is to build a string from the word list and compare it to the target, stopping early if we find a mismatch or a match.

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

Start with an empty string.
Take the first word from the list of words.
Add this word to the string we're building.
Check if the string we've built is now exactly the same as the target string. If it is, we're done and the answer is yes.
If the string we've built is longer than the target string, we know it can't be a prefix, so we're done and the answer is no.
If neither of those things happened, take the next word from the list and repeat the process from step 3.
If we run out of words from the list before matching the target string, then the target string cannot be formed by combining a prefix of the words in the list, so the answer is no.

Code Implementation

def is_prefix_string(target_string, array_of_words):
    string_builder = ""

    for word in array_of_words:
        string_builder += word

        # Early return if we have an exact match
        if string_builder == target_string:
            return True

        # Return early if the prefix exceeds the target
        if len(string_builder) > len(target_string):
            return False

    # Target can't be formed if we exhaust the word list
    return False

Big(O) Analysis

Time Complexity

O(m) – The time complexity is determined by the length of the target string 's' (denoted as m) and the combined length of the words in the input array. In the worst-case scenario, we iterate through the word array and keep appending the current word to our constructed string. The while loop continues until either the constructed string matches the target string, exceeds it, or all words are processed. The dominant operation is the string concatenation and comparison, which is bounded by the length of the target string. Hence the time complexity is O(m).

Space Complexity

O(S) – The algorithm constructs a new string by concatenating words from the input array. In the worst case, the length of this constructed string could grow proportionally to the length of the target string, which we'll call S. Therefore, the auxiliary space used for building the temporary string is O(S). There are no other significant data structures used; the space complexity is dominated by the size of the potentially large temporary string.

Edge Cases

Case	How to Handle
Null or empty string s	Return false immediately, as an empty string cannot be a prefix.
Null or empty array words	Return false immediately, as an empty array cannot create a prefix.
String s is empty but the array is not	Return true, since an empty string is a prefix of any string.
String s is very long (e.g., exceeds memory limits)	The algorithm should process s incrementally to avoid loading the entire string into memory at once.
The string s is shorter than the first word in words	Return false, because the first word alone is longer than s.
The words array contains very long strings	Handle strings of substantial length to prevent potential memory overflow or performance issues during concatenation and comparison.
The string s is formed exactly using some words but not the whole array	The solution should return true only if s is formed by the prefix of the array words.
No valid solution exists because the words array cannot form s	The solution should correctly return false if the combined words can never form s.

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 input string or any of the strings in the array be empty or null?
Are the strings in the input array guaranteed to be composed of only alphanumeric characters, or can they contain special characters or spaces?
If the string is not a prefix of the array, what should I return? Should I return false or throw an exception?
Can the same string from the array be used multiple times to form the prefix?
What are the size constraints for the input string and the strings within the array?

Brute Force Solution

Approach

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

Begin by considering just the first word from the collection of smaller words.
Check if this first word is identical to the long word. If so, we have a match!
If not, consider the first two words stuck together and check if that matches the long word.
Keep adding words, one at a time, from the collection to the growing combined word, and comparing this combined word to the long word after each addition.
If at any point the combined word becomes longer than the long word, we know it's not a prefix, and we can stop checking that particular combination.
Continue this process until we either find a match (the combined word is identical to the long word) or we have used all the words in the collection and still haven't found a match.

Code Implementation

def is_prefix_of_array(long_word, array_of_words):
    combined_word = ""

    for word in array_of_words:
        combined_word += word

        # Check if the combined word matches the long word
        if combined_word == long_word:
            return True

        # If the combined word is longer, it can't be a prefix
        if len(combined_word) > len(long_word):
            return False

    # If we get here, no prefix was found
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with an empty string.
Take the first word from the list of words.
Add this word to the string we're building.
Check if the string we've built is now exactly the same as the target string. If it is, we're done and the answer is yes.
If the string we've built is longer than the target string, we know it can't be a prefix, so we're done and the answer is no.
If neither of those things happened, take the next word from the list and repeat the process from step 3.
If we run out of words from the list before matching the target string, then the target string cannot be formed by combining a prefix of the words in the list, so the answer is no.

Code Implementation

def is_prefix_string(target_string, array_of_words):
    string_builder = ""

    for word in array_of_words:
        string_builder += word

        # Early return if we have an exact match
        if string_builder == target_string:
            return True

        # Return early if the prefix exceeds the target
        if len(string_builder) > len(target_string):
            return False

    # Target can't be formed if we exhaust the word list
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string s	Return false immediately, as an empty string cannot be a prefix.
Null or empty array words	Return false immediately, as an empty array cannot create a prefix.
String s is empty but the array is not	Return true, since an empty string is a prefix of any string.
String s is very long (e.g., exceeds memory limits)	The algorithm should process s incrementally to avoid loading the entire string into memory at once.
The string s is shorter than the first word in words	Return false, because the first word alone is longer than s.
The words array contains very long strings	Handle strings of substantial length to prevent potential memory overflow or performance issues during concatenation and comparison.
The string s is formed exactly using some words but not the whole array	The solution should return true only if s is formed by the prefix of the array words.
No valid solution exists because the words array cannot form s	The solution should correctly return false if the combined words can never form s.