Check if a String Is an Acronym of Words

Easy

Asked by:

8 views

Topics:

ArraysStringsTwo Pointers

Given an array of strings words and a string s, determine if s is an acronym of words.

The string s is considered an acronym of words if it can be formed by concatenating the first character of each string in words in order. For example, "ab" can be formed from ["apple", "banana"], but it can't be formed from ["bear", "aardvark"].

Return true if s is an acronym of words, and false otherwise.

Example 1:

Input: words = ["alice","bob","charlie"], s = "abc"
Output: true
Explanation: The first character in the words "alice", "bob", and "charlie" are 'a', 'b', and 'c', respectively. Hence, s = "abc" is the acronym.

Example 2:

Input: words = ["an","apple"], s = "a"
Output: false
Explanation: The first character in the words "an" and "apple" are 'a' and 'a', respectively. 
The acronym formed by concatenating these characters is "aa". 
Hence, s = "a" is not the acronym.

Example 3:

Input: words = ["never","gonna","give","up","on","you"], s = "ngguoy"
Output: true
Explanation: By concatenating the first character of the words in the array, we get the string "ngguoy". 
Hence, s = "ngguoy" is the acronym.

Constraints:

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

Try coding it in LeetCode

Check if a String Is an Acronym of Words

Easy

Asked by:

8 views

Topics:

ArraysStringsTwo Pointers

Given an array of strings words and a string s, determine if s is an acronym of words.

The string s is considered an acronym of words if it can be formed by concatenating the first character of each string in words in order. For example, "ab" can be formed from ["apple", "banana"], but it can't be formed from ["bear", "aardvark"].

Return true if s is an acronym of words, and false otherwise.

Example 1:

Input: words = ["alice","bob","charlie"], s = "abc"
Output: true
Explanation: The first character in the words "alice", "bob", and "charlie" are 'a', 'b', and 'c', respectively. Hence, s = "abc" is the acronym.

Example 2:

Input: words = ["an","apple"], s = "a"
Output: false
Explanation: The first character in the words "an" and "apple" are 'a' and 'a', respectively. 
The acronym formed by concatenating these characters is "aa". 
Hence, s = "a" is not the acronym.

Example 3:

Input: words = ["never","gonna","give","up","on","you"], s = "ngguoy"
Output: true
Explanation: By concatenating the first character of the words in the array, we get the string "ngguoy". 
Hence, s = "ngguoy" is the acronym.

Constraints:

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

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 contain empty strings? What should be returned in those cases?
Is the input string `s` guaranteed to be non-null or empty?
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 the length of the string `s`?
Are there any special characters or non-alphanumeric characters allowed in the strings?

Brute Force Solution

Approach

The brute force approach to checking if a string is an acronym exhaustively considers every possible way to form the acronym from the words. It's like trying every combination until you find the right one. If no combination produces the target acronym, then it is not possible.

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

Take the first letter of the first word and see if it matches the first letter of the acronym.
If it doesn't match, the words cannot form the acronym, and you're done.
If it does match, move on to the second letter of the acronym.
Now consider the first letter of the second word and check if it matches the second letter of the acronym.
Repeat this process for each subsequent word and each subsequent letter of the acronym.
If, at any point, a letter from a word doesn't match the corresponding letter in the acronym, stop and declare that these words cannot form this acronym.
If you reach the end of the words and the end of the acronym, and every letter matched, then the words do indeed form the acronym.

Code Implementation

def is_acronym_brute_force(words, acronym):
    word_index = 0
    acronym_index = 0

    while word_index < len(words) and acronym_index < len(acronym):
        # Check if the first letter of the current word matches the current letter of the acronym
        if words[word_index][0] == acronym[acronym_index]:

            acronym_index += 1
            word_index += 1

        else:
            # If it doesn't match, the words cannot form the acronym
            return False

    #If both word and acronym are exhausted, it is a match
    if word_index == len(words) and acronym_index == len(acronym):
        return True
    else:
        #Otherwise, it is not a match.
        return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the words array once, and for each word, it checks one character of the acronym. In the worst-case scenario, we process all n words in the array. This is because the algorithm sequentially compares the first letter of each word to a corresponding character in the acronym. Since the number of comparisons is directly proportional to the number of words (n), the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm iterates through the words and the acronym, comparing characters. It does not create any auxiliary data structures like lists, arrays, or hash maps to store intermediate results or visited states. The algorithm only uses a few constant space variables to keep track of the current word and acronym indices during the comparison process. Therefore, the space complexity is constant and independent of the input size, N, where N is the total number of characters in the words and acronym.

Optimal Solution

Approach

To check if a string is an acronym of a list of words, we essentially compare the first letter of each word in the list to each letter in the string. We stop if the list of words is exhausted or there's a mismatch between the letters.

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

First, get the list of words and the target string.
Go through each word in the list one by one.
At the same time, go through the characters in the target string one by one.
For each word, check if its first letter matches the current letter in the string.
If the letters match, move to the next word and the next character in the string.
If the letters don't match, the string is not an acronym, so we can stop and say it's false.
If we reach the end of the list of words and we have also reached the end of the string, then the string is a valid acronym, so return true.
If we reach the end of the list of words but there are still letters remaining in the string, then the string is not an acronym, so return false.
If we reach the end of the string but there are still words remaining in the list, the string is not an acronym, so return false.

Code Implementation

def is_acronym(words_list, target_string):    word_index = 0
    string_index = 0

    # Iterate while within bounds of both lists
    while word_index < len(words_list) and string_index < len(target_string):
        # Compare first char of word to current char in string
        if words_list[word_index][0] == target_string[string_index]:
            word_index += 1
            string_index += 1

        else:
            # If mismatch, it's not an acronym
            return False

    # Need to check if we've consumed all words and chars
    if word_index == len(words_list) and string_index == len(target_string):
        return True
    else:
        # If either list is not exhausted, not an acronym
        return False

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the number of words in the input list and the length of the target string. We iterate through the list of words and simultaneously through the characters of the string. The maximum number of iterations will be limited by the shorter of the two. In the worst case, we process each word and each character once. Therefore, the time complexity is linear, O(n), where n represents the number of words in the list (or the length of the string if the string is shorter).

Space Complexity

O(1) – The algorithm iterates through the input list of words and the target string using index variables. The plain english description doesn't mention creating any auxiliary data structures like new lists, hashmaps, or recursion stack frames. The space required for these index variables is constant, irrespective of the number of words or the length of the string. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
words is null or empty	Return true if s is also empty, otherwise return false, as an empty list of words can only produce an empty acronym.
s is null or empty	Return true if words is also empty, otherwise return false as an empty string cannot be an acronym for a non-empty word list.
words contains an empty string	If an empty string is in the words array, its first character should be treated as empty, potentially still producing a valid acronym if other words align.
words contains strings of varying lengths	The solution should correctly extract the first character regardless of the string length.
s is shorter than the combined length of the first characters of words	The acronym cannot be formed, return false, as s does not contain all the prefixes.
s is longer than the combined length of the first characters of words	The acronym cannot be formed, return false, as s contains more characters than can be created by prefixes
words array has very large number of strings, approaching memory limits	The iterative approach avoids deep recursion, thus preventing stack overflow and is memory-efficient.
words array contains strings with non-alphabetic characters.	The solution should treat each character as is, including special chars/numbers, when comparing with characters in s.