Check if a String Is an Acronym of Words

Difficulty: Easy | Acceptance: 83.00% | Paid: No Topics: Array, String

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

The string s is an acronym of words if it can be formed by concatenating the first character of each string in words in order. For example, [“ab”, “c”] forms the acronym “ac”.

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

• Examples
• Constraints
• Iterative Comparison
• Two Pointers

Examples

Input: words = ["alice","bob","charlie"], s = "abc"
Output: true
Explanation: The first character of the words "alice", "bob", and "charlie" are 'a', 'b', and 'c' respectively. s = "abc" is the acronym formed by concatenating these characters, so return true.

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

Input: words = ["never","gonna","give","up","on","you"], s = "ngguoy"
Output: true

Constraints

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

Iterative Comparison

Intuition We can construct the acronym string by iterating through the words array and appending the first character of each word to a result string. Finally, we compare the constructed string with s.

Steps

• Initialize an empty string builder or result string.
• Iterate through each word in the words array.
• Append the first character of the current word to the result.
• After the loop, compare the result with s.
• Return true if they are equal, false otherwise.

class Solution:
    def isAcronym(self, words: list[str], s: str) -> bool:
        return ''.join(w[0] for w in words) == s

Complexity

• Time: O(N), where N is the total number of characters in the words array (specifically the number of words).
• Space: O(N), to store the constructed acronym string.
• Notes: This approach is straightforward and readable, but uses extra space proportional to the length of the acronym.

Two Pointers

Intuition We can optimize space by comparing characters on the fly without building a new string. If the length of words is different from the length of s, they cannot be acronyms. Otherwise, we check if the first character of each word matches the corresponding character in s.

Steps

• Check if the length of words is equal to the length of s. If not, return false.
• Iterate through the indices of the words array.
• At each index i, check if words[i][0] is equal to s[i].
• If any character does not match, return false.
• If the loop completes without mismatches, return true.

class Solution:
    def isAcronym(self, words: list[str], s: str) -> bool:
        if len(words) != len(s):
            return False
        for i in range(len(words)):
            if words[i][0] != s[i]:
                return False
        return True

Complexity

• Time: O(N), where N is the number of words.
• Space: O(1), as we only use a constant amount of extra space for variables.
• Notes: This is the most optimal approach in terms of space complexity.