To find all the words from the first array that have an anagram in the second array, we can utilize sorting and sets for efficient matching. Here's how we can implement this in TypeScript:
function sortCharacters(input: string): string {
return [...input].sort().join('');
}
function findAnagrams(array1: string[], array2: string[]): string[] {
let sortedWordsInArray2: Set<string> = new Set();
array2.forEach(word => sortedWordsInArray2.add(sortCharacters(word)));
let result: string[] = [];
for (const word of array1) {
const sortedWord = sortCharacters(word);
if (sortedWordsInArray2.has(sortedWord)) {
result.push(word);
}
}
return result;
}
Explanation:
-
Character Sorting:
- We define a helper function
sortCharacters to generate a sorted string of characters from any input string. This sorted string acts as a signature for identifying anagrams, as anagrams share the same characters in possibly different orders.
- The function converts the input string to an array of its characters, sorts them, and concatenates them back to a string.
-
Storing Anagram Signatures:
- We create a set
sortedWordsInArray2 to store unique sorted character signatures from each word in array2. Using a set allows for efficient lookup operations, vital for later steps.
-
Finding Anagrams:
- For each word in
array1, we generate its sorted signature using sortCharacters. We then check if this signature exists in sortedWordsInArray2.
- If a match is found, the original word from
array1 is an anagram of a word in array2, and we add it to the result array.
-
Return:
- Finally, the
result array, which contains all words from array1 that have an anagram in array2, is returned.
For the example arrays ["listen", "google"] and ["inlets", "banana", "gogle"], the output would be ["listen"].
By utilizing sets and character sorting, we can efficiently check for anagrams with minimal computational overhead, balancing both the sorting complexity O(mlogm) for each word and the O(n) comparison for n words.
