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"]
ands = "ab"
, thens
is an acronym because'a'
(first letter of "apple") +'b'
(first letter of "banana") ="ab"
- If
words = ["bear", "aardvark"]
ands = "ab"
, thens
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
.
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:
- We need ALL first letters to match in the exact order
- The length must also match (if
words
has 3 words, the acronym must have exactly 3 characters) - 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:
-
Extract First Characters: We iterate through each word in the
words
array and extract the first character using indexingw[0]
. This gives us a sequence of first letters. -
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. -
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)
wheren
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 EvaluatorExample 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
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!