966. Vowel Spellchecker #

Problem #

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
- Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
- Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
- Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
- Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
- Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
- Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
When the query matches a word up to capitlization, you should return the first such match in the wordlist.
When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input:wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output:["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Note:

1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
All strings in wordlist and queries consist only of english letters.

Problem Summary #

Given a word list wordlist, we want to implement a spellchecker that converts a query word into the correct word.

For a given query word query, the spellchecker will handle two types of spelling mistakes:

Capitalization: If the query matches a word in the word list (case-insensitive), then the correct word returned has the same capitalization as the word in the word list.
- Example: wordlist = [“yellow”], query = “YellOw”: correct = “yellow”
- Example: wordlist = [“Yellow”], query = “yellow”: correct = “Yellow”
- Example: wordlist = [“yellow”], query = “yellow”: correct = “yellow”
Vowel Errors: If, after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) in the query word with any vowel individually, it can match a word in the word list (case-insensitive), then the correct word returned has the same capitalization as the matching item in the word list.
- Example: wordlist = [“YellOw”], query = “yollow”: correct = “YellOw”
- Example: wordlist = [“YellOw”], query = “yeellow”: correct = "” (no match)
- Example: wordlist = [“YellOw”], query = “yllw”: correct = "” (no match)

In addition, the spellchecker also operates according to the following precedence rules:

When the query exactly matches a word in the word list (case-sensitive), the same word should be returned.
When the query matches a word with a capitalization issue, you should return the first such match in the word list.
When the query matches a word with a vowel error, you should return the first such match in the word list.
If the query has no match in the word list, an empty string should be returned.

Given some queries queries, return a word list answer, where answer[i] is the correct word obtained from query query = queries[i].

Solution Approach #

After reading the problem, it is obvious that map is needed to solve it. According to the problem statement, there are 3 cases: the query string matches exactly; the query string differs only in capitalization; the query string has a vowel error. For the first case, use a map key to match directly. For the second case, use a map to convert the lowercase form of a word into the original word with the correct capitalization. For the third case, use a map to convert the lowercase form of a word with vowels ignored into the original correct form. Finally, just pay attention to the 4 precedence rules given at the end of the problem.

Code #

package leetcode

import "strings"

func spellchecker(wordlist []string, queries []string) []string {
	wordsPerfect, wordsCap, wordsVowel := map[string]bool{}, map[string]string{}, map[string]string{}
	for _, word := range wordlist {
		wordsPerfect[word] = true
		wordLow := strings.ToLower(word)
		if _, ok := wordsCap[wordLow]; !ok {
			wordsCap[wordLow] = word
		}
		wordLowVowel := devowel(wordLow)
		if _, ok := wordsVowel[wordLowVowel]; !ok {
			wordsVowel[wordLowVowel] = word
		}
	}
	res, index := make([]string, len(queries)), 0
	for _, query := range queries {
		if _, ok := wordsPerfect[query]; ok {
			res[index] = query
			index++
			continue
		}
		queryL := strings.ToLower(query)
		if v, ok := wordsCap[queryL]; ok {
			res[index] = v
			index++
			continue
		}

		queryLV := devowel(queryL)
		if v, ok := wordsVowel[queryLV]; ok {
			res[index] = v
			index++
			continue
		}
		res[index] = ""
		index++
	}
	return res

}

func devowel(word string) string {
	runes := []rune(word)
	for k, c := range runes {
		if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
			runes[k] = '*'
		}
	}
	return string(runes)
}