Facebook Pixel

2828. Check if a String Is an Acronym of Words

Problem Description

You are given an array of strings words and a string s. Your task is to determine if s is an acronym of the words in the array.

A string s is considered an acronym of words if it can be formed by taking the first character of each string in words and concatenating them together in the same order they appear in the array.

For example:

  • If words = ["apple", "banana"] and s = "ab", then s is an acronym because 'a' (first letter of "apple") + 'b' (first letter of "banana") = "ab"
  • If words = ["bear", "aardvark"] and s = "ab", then s is NOT an acronym because 'b' (first letter of "bear") + 'a' (first letter of "aardvark") = "ba", which doesn't equal "ab"

The function should return true if s is an acronym of words, and false otherwise.

The solution works by iterating through each word in the words array, extracting the first character of each word using w[0], joining all these first characters together with "".join(), and then comparing the resulting string with s. If they match, the function returns true; otherwise, it returns false.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The problem asks us to check if a given string is formed by the first letters of words in an array. The most straightforward way to verify this is to actually construct what the acronym would be and compare it with the given string.

Think of it like checking if someone correctly created an acronym - we would go through each word, take its first letter, and see if putting them all together matches what they gave us. There's no need for complex logic here since we just need a direct comparison.

The key insight is that we don't need to check character by character as we go. Instead, we can build the complete acronym string first and then do a single comparison. This is because:

  1. We need ALL first letters to match in the exact order
  2. The length must also match (if words has 3 words, the acronym must have exactly 3 characters)
  3. A single string comparison handles both the content and length check simultaneously

By using "".join(w[0] for w in words), we efficiently extract the first character from each word and concatenate them into a single string. This one-liner approach leverages Python's generator expression to avoid creating intermediate lists, making it both readable and efficient. The final == s comparison gives us our boolean result directly.

Solution Approach

The solution uses a simulation approach where we directly construct the acronym from the given words and compare it with the target string s.

Implementation Steps:

  1. Extract First Characters: We iterate through each word in the words array and extract the first character using indexing w[0]. This gives us a sequence of first letters.

  2. Concatenate Characters: Using Python's "".join() method, we concatenate all the extracted first characters into a single string. The generator expression (w[0] for w in words) creates an iterator that yields the first character of each word without creating an intermediate list.

  3. Comparison: We directly compare the constructed string with s using the equality operator ==. This comparison checks both:

    • Whether the characters match in the same order
    • Whether the lengths are equal (implicit in string equality)

Algorithm Details:

The entire process can be expressed as:

  • Time Complexity: O(n) where n is the number of words in the array, as we visit each word exactly once
  • Space Complexity: O(n) for creating the concatenated string of first characters

The beauty of this solution lies in its simplicity - rather than using complex logic with multiple conditions or loops, we leverage Python's built-in string operations to solve the problem in a single line. The "".join() method efficiently handles the concatenation, and the string comparison gives us the final boolean result directly.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a concrete example to see how it works step by step.

Example:

  • words = ["alice", "bob", "charlie"]
  • s = "abc"

Step 1: Extract First Characters

We go through each word and extract its first character:

  • "alice" → first character is 'a'
  • "bob" → first character is 'b'
  • "charlie" → first character is 'c'

Step 2: Build the Acronym String

Using "".join(w[0] for w in words):

  • The generator expression w[0] for w in words produces: 'a', 'b', 'c'
  • "".join() concatenates these characters: "abc"

Step 3: Compare with Target String

We compare our constructed acronym with s:

  • Constructed acronym: "abc"
  • Given string s: "abc"
  • Comparison: "abc" == "abc" → true

The function returns true because the string matches the acronym.

Counter-Example:

If we had s = "bac" instead:

  • Constructed acronym: "abc" (same as before)
  • Given string s: "bac"
  • Comparison: "abc" == "bac" → false

The function returns false because even though the letters are the same, the order doesn't match. This demonstrates why building the complete acronym and comparing is effective - it naturally handles both character matching and ordering in one operation.

Solution Implementation

1class Solution:
2    def isAcronym(self, words: List[str], s: str) -> bool:
3        """
4        Check if the given string s is an acronym of the words list.
5        An acronym is formed by concatenating the first character of each word.
6      
7        Args:
8            words: List of strings representing words
9            s: Target string to check if it's an acronym
10          
11        Returns:
12            bool: True if s is an acronym of words, False otherwise
13        """
14        # Extract the first character from each word and join them together
15        acronym = "".join(word[0] for word in words)
16      
17        # Check if the formed acronym matches the target string
18        return acronym == s
19
1class Solution {
2    /**
3     * Checks if a string is an acronym formed by the first characters of words in a list.
4     * 
5     * @param words List of strings to form the acronym from
6     * @param s     Target string to compare against the formed acronym
7     * @return      true if s equals the acronym formed from first characters of words, false otherwise
8     */
9    public boolean isAcronym(List<String> words, String s) {
10        // Build the acronym by concatenating first characters
11        StringBuilder acronym = new StringBuilder();
12      
13        // Iterate through each word in the list
14        for (String word : words) {
15            // Append the first character of current word to the acronym
16            acronym.append(word.charAt(0));
17        }
18      
19        // Check if the formed acronym equals the target string
20        return acronym.toString().equals(s);
21    }
22}
23
1class Solution {
2public:
3    /**
4     * Check if the given string s is an acronym of the words array.
5     * An acronym is formed by concatenating the first character of each word.
6     * 
7     * @param words - vector of strings representing the words
8     * @param s - target string to check against the acronym
9     * @return true if s matches the acronym, false otherwise
10     */
11    bool isAcronym(vector<string>& words, string s) {
12        // Build the acronym by collecting first characters
13        string acronym;
14      
15        // Iterate through each word in the vector
16        for (const auto& word : words) {
17            // Append the first character of current word to acronym
18            acronym += word[0];
19        }
20      
21        // Check if the constructed acronym matches the target string
22        return acronym == s;
23    }
24};
25
1/**
2 * Checks if a string is an acronym formed from the first letters of given words
3 * @param words - Array of words to form the acronym from
4 * @param s - Target string to check against
5 * @returns true if s is the acronym of words, false otherwise
6 */
7function isAcronym(words: string[], s: string): boolean {
8    // Extract the first character from each word and join them together
9    const acronym: string = words.map((word: string) => word[0]).join('');
10  
11    // Check if the formed acronym matches the target string
12    return acronym === s;
13}
14

Time and Space Complexity

The time complexity is O(n), where n is the length of the array words. This is because the generator expression iterates through each word in the list exactly once to extract the first character.

The space complexity is O(n), where n is the length of the array words. Although a generator expression is used, the "".join() method needs to materialize all the first characters into a string before performing the comparison. This creates a new string with length equal to the number of words, which requires O(n) space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Empty String Handling

One of the most common pitfalls is not considering edge cases with empty strings in the words array. If any word in the array is an empty string, accessing word[0] will raise an IndexError.

Example of the problem:

words = ["apple", "", "cat"]
s = "ac"
# This will crash with IndexError: string index out of range

Solution: Add a check to handle empty strings:

def isAcronym(self, words: List[str], s: str) -> bool:
    # Filter out empty strings or check before accessing
    acronym = "".join(word[0] for word in words if word)
    return acronym == s

Or with explicit validation:

def isAcronym(self, words: List[str], s: str) -> bool:
    # Validate that all words are non-empty
    if any(not word for word in words):
        return False  # or handle according to requirements
    acronym = "".join(word[0] for word in words)
    return acronym == s

2. Case Sensitivity Assumptions

The current solution is case-sensitive, which means "Apple" and "apple" would produce different acronyms ('A' vs 'a'). This might not align with the problem requirements if case-insensitive matching is expected.

Example of the problem:

words = ["Apple", "Banana", "Cherry"]
s = "abc"  # Returns False, but might expect True

Solution: Normalize the case if case-insensitive comparison is needed:

def isAcronym(self, words: List[str], s: str) -> bool:
    acronym = "".join(word[0].lower() for word in words if word)
    return acronym == s.lower()

3. Unicode and Special Characters

The solution assumes all strings contain valid characters, but special Unicode characters or whitespace at the beginning of words could cause unexpected behavior.

Example of the problem:

words = [" apple", "\nbanana", "cherry"]  # Leading whitespace
s = " \nc"  # Would match but probably shouldn't

Solution: Strip whitespace and validate characters:

def isAcronym(self, words: List[str], s: str) -> bool:
    # Strip whitespace from words before processing
    acronym = "".join(word.strip()[0] for word in words if word.strip())
    return acronym == s

4. Memory Optimization for Large Inputs

While the current solution is efficient, for extremely large arrays, creating the full acronym string before comparison uses unnecessary memory when early termination is possible.

Solution for optimization: Check character by character for early termination:

def isAcronym(self, words: List[str], s: str) -> bool:
    # Early termination if lengths don't match
    if len(words) != len(s):
        return False
  
    # Check character by character
    for i, word in enumerate(words):
        if not word or word[0] != s[i]:
            return False
    return True

This approach provides better performance by:

  • Checking length compatibility upfront
  • Terminating early on the first mismatch
  • Avoiding string concatenation overhead
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More