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)
}