Given an array of words and an array of sentences, calculate how many distinct sentences can be created by replacing any word with one of its anagrams.
Note:
• Two words are said to be anagrams of each other if one can be created by rearranging the letters of the other word, using all the original letters exactly once.
Example:
wordSet = [‘listen’,‘silent’,‘it’,‘is’]
sentence =“listen it is silent”
Determine that“listen”is an anagram of“silent”. Those two words can be replaced with their anagrams. The four sentences that can be created are:
• listen it is silent
• listen it is listen
• silent it is silent
• silent it is listen
Function Description
Complete the function countSentences in the editor below.
countSentences has the following parameters:
• string wordSet[n]: an array of strings
• string sentences[m]: an array of strings (each sentence is space-separated words)
Return:
• long integer array: for each sentence, the number of distinct sentences that can be formed by replacing words with any of their anagrams from wordSet.
Constraints:
• All strings are lowercase English letters.
• 1 ≤ n, m ≤ reasonable limits for typical interview problems.
• Words appear in sentences only if they exist in wordSet (or you may assume nonexistent words contribute a factor of 1).
Group words in wordSet by their sorted-letters signature. For each sentence, split into words and multiply the group sizes of each word’s signature to get the total number of distinct sentences. Complexity: building the map O(N·LlogL); per sentence O(K·LlogL), where L is average word length and K is words per sentence.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Oracle, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for these companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
