Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/966.html

966. Vowel Spellchecker

Level

Medium

Description

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.

Solution

Add all the words in wordlist to a set, and use two maps to store the lower case version and the devoweled version (where each vowel is replace by another character) of each word respectively.

For each string in query, first check whether the string is in the set. If so, this is an exact match, so return the same word as the match word.

If no exact match is found, then check whether there is a match that contains exactly the same letters ignoring case. If so, return the first such word in wordlist as the match word.

If no same word ignoring case is found, then check whether there is a devowel match. If so, return the first such word in wordlist as the match word.

If no devowel match is found, return an empty string as the match word.

  • class Solution {
    Set<String> match;
    Map<String, String> matchIgnoreCase;
    Map<String, String> matchIgnoreVowel;

    public String[] spellchecker(String[] wordlist, String[] queries) {
        match = new HashSet<String>();
        matchIgnoreCase = new HashMap<String, String>();
        matchIgnoreVowel = new HashMap<String, String>();
        int listLength = wordlist.length;
        for (int i = 0; i < listLength; i++) {
            String word = wordlist[i];
            match.add(word);
            String wordLower = word.toLowerCase();
            matchIgnoreCase.putIfAbsent(wordLower, word);
            String deVowel = deVowel(wordLower);
            matchIgnoreVowel.putIfAbsent(deVowel, word);
        }
        int length = queries.length;
        String[] answer = new String[length];
        for (int i = 0; i < length; i++) {
            String query = queries[i];
            String queryLower = query.toLowerCase();
            String queryLowerDeVowel = deVowel(queryLower);
            if (match.contains(query))
                answer[i] = query;
            else if (matchIgnoreCase.containsKey(queryLower))
                answer[i] = matchIgnoreCase.get(queryLower);
            else if (matchIgnoreVowel.containsKey(queryLowerDeVowel))
                answer[i] = matchIgnoreVowel.get(queryLowerDeVowel);
            else
                answer[i] = "";
        }
        return answer;
    }

    public String deVowel(String str) {
        char[] array = str.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; i++) {
            if (isVowel(array[i]))
                array[i] = '.';
        }
        return new String(array);
    }

    public boolean isVowel(char c) {
        return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' || c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

  • class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def f(w):
            t = []
            for c in w:
                t.append("*" if c in "aeiou" else c)
            return "".join(t)

        s = set(wordlist)
        low, pat = {}, {}
        for w in wordlist:
            t = w.lower()
            low.setdefault(t, w)
            pat.setdefault(f(t), w)

        ans = []
        for q in queries:
            if q in s:
                ans.append(q)
                continue
            q = q.lower()
            if q in low:
                ans.append(low[q])
                continue
            q = f(q)
            if q in pat:
                ans.append(pat[q])
                continue
            ans.append("")
        return ans

############

class Solution(object):
    def spellchecker(self, wordlist, queries):
        """
        :type wordlist: List[str]
        :type queries: List[str]
        :rtype: List[str]
        """
        wordset = set(wordlist)
        capdict = {word.lower() : word for word in wordlist[::-1]}
        vodict = {re.sub(r'[aeiou]', '#', word.lower()) : word for word in wordlist[::-1]}
        res = []
        for q in queries:
            if q in wordset:
                res.append(q)
            elif q.lower() in capdict:
                res.append(capdict[q.lower()])
            elif re.sub(r'[aeiou]', '#', q.lower()) in vodict:
                res.append(vodict[re.sub(r'[aeiou]', '#', q.lower())])
            else:
                res.append("")
        return res

  • class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> s(wordlist.begin(), wordlist.end());
        unordered_map<string, string> low;
        unordered_map<string, string> pat;
        auto f = [](string& w) {
            string res;
            for (char& c : w) {
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    res += '*';
                } else {
                    res += c;
                }
            }
            return res;
        };
        for (auto& w : wordlist) {
            string t = w;
            transform(t.begin(), t.end(), t.begin(), ::tolower);
            if (!low.count(t)) {
                low[t] = w;
            }
            t = f(t);
            if (!pat.count(t)) {
                pat[t] = w;
            }
        }
        vector<string> ans;
        for (auto& q : queries) {
            if (s.count(q)) {
                ans.emplace_back(q);
                continue;
            }
            transform(q.begin(), q.end(), q.begin(), ::tolower);
            if (low.count(q)) {
                ans.emplace_back(low[q]);
                continue;
            }
            q = f(q);
            if (pat.count(q)) {
                ans.emplace_back(pat[q]);
                continue;
            }
            ans.emplace_back("");
        }
        return ans;
    }
};

  • func spellchecker(wordlist []string, queries []string) (ans []string) {
	s := map[string]bool{}
	low := map[string]string{}
	pat := map[string]string{}
	f := func(w string) string {
		res := []byte(w)
		for i := range res {
			if res[i] == 'a' || res[i] == 'e' || res[i] == 'i' || res[i] == 'o' || res[i] == 'u' {
				res[i] = '*'
			}
		}
		return string(res)
	}
	for _, w := range wordlist {
		s[w] = true
		t := strings.ToLower(w)
		if _, ok := low[t]; !ok {
			low[t] = w
		}
		if _, ok := pat[f(t)]; !ok {
			pat[f(t)] = w
		}
	}
	for _, q := range queries {
		if s[q] {
			ans = append(ans, q)
			continue
		}
		q = strings.ToLower(q)
		if s, ok := low[q]; ok {
			ans = append(ans, s)
			continue
		}
		q = f(q)
		if s, ok := pat[q]; ok {
			ans = append(ans, s)
			continue
		}
		ans = append(ans, "")
	}
	return
}

All Problems

All Solutions