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 <= 1001 <= words[i].length <= 101 <= s.length <= 100words[i] and s consist of lowercase English letters.Problem Overview: You receive an array of words and a string s. The task is to determine whether s equals the acronym formed by taking the first character of every word in the array, in order.
Approach 1: Iterative String Concatenation (O(n) time, O(n) space)
Build the acronym explicitly. Iterate through the array of words and append the first character of each word to a temporary string. After the loop, compare the generated acronym with s. If both strings are identical, return true; otherwise return false. This approach is straightforward and easy to reason about because you recreate the expected acronym before comparing it.
The main cost comes from constructing the new string, which requires O(n) time for n words and O(n) extra space to store the acronym. This approach is useful when clarity is more important than strict memory efficiency.
Approach 2: Index-Based Character Matching (O(n) time, O(1) space)
A more space-efficient approach compares characters directly without building a new string. First check if s.length() equals the number of words. If the lengths differ, the acronym cannot match. Then iterate through the word list and compare the first character of each word with the corresponding character in s.
If any comparison fails, return false immediately. If the loop completes successfully, the acronym matches and you return true. This method relies on simple index access in a string and sequential traversal of the array.
The algorithm runs in O(n) time because each word is inspected once. Space complexity is O(1) since no additional data structures are created. The early length check also prevents unnecessary comparisons.
Recommended for interviews: Index-Based Character Matching is typically expected. It demonstrates awareness of unnecessary allocations and keeps the solution clean and efficient. Showing the concatenation approach first proves you understand the problem transformation, but the index-based method shows stronger attention to space optimization and early validation checks.
This approach involves iterating over each word, extracting the first character, and concatenating these characters to form a new string. Finally, compare this concatenated string with the string s. If they are equal, s is an acronym; otherwise, it is not.
This C code iterates through each word in the array to collect the first character, concatenates them into a string, and compares this new string with s using strcmp.
Time Complexity: O(n), where n is the length of `words`.
Space Complexity: O(1), aside from input storage.
For this approach, directly compare the i-th character in s with the first character of the i-th word in words. This eliminates the need for an additional string construction, thus potentially speeding up the execution by doing the comparison simultaneously during the iteration.
This C solution checks if the length of `s` matches the number of words. If not, it directly returns false. Otherwise, it iterates over each word and checks if the corresponding character in `s` matches the first character of the word.
Time Complexity: O(n), where n is the length of `s` (or words since they must be the same).
Space Complexity: O(1).
We can iterate over each string in the array words, concatenate their first letters to form a new string t, and then check if t is equal to s.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array words.
First, we check if the number of strings in words is equal to the length of s. If not, s is definitely not an acronym of the first letters of words, and we directly return false.
Then, we iterate over each character in s, checking if it is equal to the first letter of the corresponding string in words. If not, s is definitely not an acronym of the first letters of words, and we directly return false.
After the iteration, if we haven't returned false, then s is an acronym of the first letters of words, and we return true.
The time complexity is O(n), where n is the length of the array words. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative String Concatenation | Time Complexity: O(n), where n is the length of `words`. |
| Index-Based Character Matching | Time Complexity: O(n), where n is the length of `s` (or |
| Simulation | — |
| Simulation (Space Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative String Concatenation | O(n) | O(n) | When readability and explicit acronym construction help understanding |
| Index-Based Character Matching | O(n) | O(1) | General case and interview settings where constant space is preferred |
Leetcode | 2828. Check if a String is an Acronym of Words | Easy | Java Solution • Developer Docs • 741 views views
Watch 9 more video solutions →Practice Check if a String Is an Acronym of Words with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor