Check if a String Is an Acronym of Words
EasyPrompt
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]andsconsist of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves first constructing the potential acronym from the words list and then comparing it with the given string s.
Algorithm
- Initialize an empty
StringBuilder. - Iterate through each
wordin thewordslist. - Append the first character of the
word(word.charAt(0)) to theStringBuilder. - After the loop, convert the
StringBuilderto a string. - Return the result of comparing this new string with
s.
Walkthrough
This method directly translates the problem definition into code. It uses a StringBuilder for efficient string concatenation. We iterate through the list of words, appending the first character of each word to the StringBuilder. Once the full acronym string is built, it is converted to a String and compared with the input string s. While this is very clear and easy to implement, it requires additional memory to hold the newly constructed string.
import java.util.List; class Solution { public boolean isAcronym(List<String> words, String s) { StringBuilder acronymBuilder = new StringBuilder(); for (String word : words) { acronymBuilder.append(word.charAt(0)); } return acronymBuilder.toString().equals(s); }}Complexity
Time
`O(N)`, where `N` is the number of strings in `words`. The loop runs `N` times, and the final string comparison also takes `O(N)` time.
Space
`O(N)`, as a `StringBuilder` (and then a `String`) of length `N` is created to store the acronym, where `N` is the number of words.
Trade-offs
Pros
Very straightforward and easy to understand.
Code directly reflects the problem's definition.
Cons
Inefficient in terms of space usage.
Builds the entire string even if a mismatch could be found early, such as differing lengths.
A more efficient approach is to compare the characters directly without constructing an intermediate acronym string. This saves space and can be faster by allowing for an early exit.
Algorithm
- First, check if
words.size()is equal tos.length(). If not, returnfalse. - Iterate with an index
ifrom0towords.size() - 1. - In each iteration, check if
words.get(i).charAt(0)is not equal tos.charAt(i). - If they are not equal, return
false. - If the loop completes, it means all characters matched, so return
true.
Walkthrough
This optimized method avoids the overhead of creating a new string. It starts with a quick and crucial check: if the number of words doesn't match the length of the string s, it's impossible for s to be the acronym, so we can return false immediately. If the lengths are equal, we proceed to a single loop. The loop iterates through the indices from 0 to N-1, comparing the first character of the i-th word with the i-th character of s. If a mismatch is found at any point, we can stop and return false. If the loop completes without any mismatches, it confirms that s is the correct acronym, and we return true.
import java.util.List; class Solution { public boolean isAcronym(List<String> words, String s) { if (words.size() != s.length()) { return false; } for (int i = 0; i < words.size(); i++) { if (words.get(i).charAt(0) != s.charAt(i)) { return false; } } return true; }}Complexity
Time
`O(N)`, where `N` is `words.size()`. In the best case (unequal lengths), it's `O(1)`. In the worst case, it iterates through all `N` words once.
Space
`O(1)`. This approach uses a constant amount of extra memory, making it highly space-efficient.
Trade-offs
Pros
Optimal space complexity of
O(1).Faster in many cases due to early exit on length mismatch or character mismatch.
Cons
The logic is slightly less direct than building the string, involving an explicit loop with an index and conditions.
Solutions
Solution
class Solution {public boolean isAcronym(List<String> words, String s) { StringBuilder t = new StringBuilder(); for (var w : words) { t.append(w.charAt(0)); } return t.toString().equals(s); }}class Solution {public: bool isAcronym(vector<string> &words, string s) { string t; for (auto &w : words) { t += w[0]; } return t == s; }};class Solution: def isAcronym( self, words: List[str], s: str) -> bool: return "" . join(w[0] for w in words) == sVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.