Sponsored
Sponsored
This approach uses three types of hash maps:
Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), to store the dictionaries for the wordlist.
1import java.util.*;
2public class VowelSpellchecker {
3 public String[] spellchecker(String[] wordlist, String[] queries) {
4 Set<String> exactMatches = new HashSet<>(Arrays.asList(wordlist));
5 Map<String, String> caseSensitiveMatches = new HashMap<>();
6 Map<String, String> vowelInsensitiveMatches = new HashMap<>();
7
8 for (int i = wordlist.length - 1; i >= 0; i--) {
9 String word = wordlist[i];
10 String lower = word.toLowerCase();
11 String vowelMask = maskVowels(lower);
12 caseSensitiveMatches.putIfAbsent(lower, word);
13 vowelInsensitiveMatches.putIfAbsent(vowelMask, word);
14 }
15
16 String[] result = new String[queries.length];
17
18 for (int i = 0; i < queries.length; i++) {
19 String query = queries[i];
20 if (exactMatches.contains(query)) {
21 result[i] = query;
22 } else {
23 String lowerQuery = query.toLowerCase();
24 String maskedQuery = maskVowels(lowerQuery);
25
26 if (caseSensitiveMatches.containsKey(lowerQuery)) {
27 result[i] = caseSensitiveMatches.get(lowerQuery);
28 } else if (vowelInsensitiveMatches.containsKey(maskedQuery)) {
29 result[i] = vowelInsensitiveMatches.get(maskedQuery);
30 } else {
31 result[i] = "";
32 }
33 }
34 }
35 return result;
36 }
37
38 private String maskVowels(String word) {
39 char[] c = word.toCharArray();
40 for (int i = 0; i < c.length; i++) {
41 if ("aeiou".indexOf(c[i]) >= 0) {
42 c[i] = '*';
43 }
44 }
45 return new String(c);
46 }
47}This Java solution uses a similar logic to the Python implementation. It keeps track of potential matches using three collections: a set for exact matches, a map for case-insensitive matches, and another map for vowel-insensitive matches. The method maskVowels is used to transform words so vowels are replaced with a placeholder, facilitating vowel-error detection.
This approach utilizes a trie data structure to accommodate the various search conditions:
Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), for storing each transformed mapping in the maps used.
1function spellchecker(wordlist,
This JavaScript implementation captures the essence of the trie strategy using objects. It leverages function maskVowels to replace vowels with asterisks for vowel-insensitive matching. The solution goes through a sequential check for matches and returns the correct form based on the first match success.