LeetCode: Vowel Spellchecker

Vowel Spellchecker

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #hashmap, #string

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/vowel-spellchecker
// Basic Ideas: String + hashmap
//
// Complexity: Time O(n) Space O(n)
func spellchecker(wordlist []string, queries []string) []string {
    words := map[string]int{}
    words2 := map[string]int{}
    words3 := map[string]int{}
    for k, w := range wordlist {
        words[w] = k
        bytes := make([]byte, len(w))
        for i, _ := range w {
            ch := w[i]
            if ch >= 'A' && ch <= 'Z' {
                bytes[i] = ch - 'A' + 'a'
            } else {
                bytes[i] = ch
            }
        }
        w2 := string(bytes)
        if _, ok := words2[w2]; !ok {
            words2[w2] = k
        }
        for i, b := range bytes {
            if b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' {
                bytes[i] = '*'
            }
        }
        w3 := string(bytes)
        if _, ok := words3[w3]; !ok {
            words3[w3] = k
        }
    }
    res := make([]string, len(queries))
    for k, q := range queries {
        // exact match
        if _, ok := words[q]; ok {
            res[k] = q
            continue
        }
        // capitalization match
        bytes := []byte(q)
        for i, _ := range q {
            ch := q[i]
            if ch >= 'A' && ch <= 'Z' {
                bytes[i] = ch - 'A' + 'a'
            }
        }
        q2 := string(bytes)
        if pos, ok := words2[q2]; ok {
            res[k] = wordlist[pos]
            continue
        }
        // Vowel Errors
        for i, b := range bytes {
            if b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' {
                bytes[i] = '*'
            }
        }
        q3 := string(bytes)
        if pos, ok := words3[q3]; ok {
            res[k] = wordlist[pos]
        }
    }
    return res
}