Count Phrases Formed by Anagram Replacement
Wells Fargo● EasyINTERNOAProblem statement
Two words are anagrams when one can be made by rearranging all the letters of the other. A word counts as an anagram of itself.
You are given an array words of different lowercase words and an array phrases. Each phrase is a small sentence made from words in words, separated by single spaces.
To make a new phrase, replace each word of a phrase with any of its anagrams from words. Each position chooses on its own, even when the same word appears more than once. The original phrase is one of the results.
Return an array answer where answer[i] is the number of phrases that can be made from phrases[i].
Function
countPhrases(words: String[], phrases: String[]) → long[]Examples
Example 1
words = ["stop","pots","tops","on","no","go"]phrases = ["stop on go","go no"]return = [6,2]stop has 3 anagrams in words: stop, pots, and tops. on has 2: on and no. go has only itself.
"stop on go"can be made in3 * 2 * 1 = 6ways."go no"can be made in1 * 2 = 2ways:"go no"and"go on".
Example 2
words = ["ab","ba","cat"]phrases = ["ab ab","ab ba cat"]return = [4,4]Each position chooses on its own, even when the same word appears twice.
"ab ab"gives"ab ab","ab ba","ba ab", and"ba ba", so the count is2 * 2 = 4."ab ba cat"gives2 * 2 * 1 = 4, becausecathas only itself.
Example 3
words = ["aab","aba","abb"]phrases = ["aab","abb","aba abb"]return = [2,1,2]Anagrams must use each letter the same number of times. aab and aba are anagrams, but abb is not an anagram of them even though it uses the same two letters.
"aab"has 2 choices."abb"has 1 choice."aba abb"has2 * 1 = 2choices.
Constraints
1 <= words.length <= 20001 <= words[i].length <= 20words[i]contains only lowercase English letters.- All strings in
wordsare different. 1 <= phrases.length <= 500- Each
phrases[i]has1to20words, separated by single spaces, with no space at the start or end. - Every word in a phrase appears in
words. - Each answer is at most
10^15.