Welcome to Subscribe On Youtube

966. Vowel Spellchecker

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"]

Example 2:

Input: wordlist = ["yellow"], queries = ["YellOw"]
Output: ["yellow"]

 

Constraints:

• 1 <= wordlist.length, queries.length <= 5000
• 1 <= wordlist[i].length, queries[i].length <= 7
• wordlist[i] and queries[i] consist only of only English letters.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public String[] spellchecker(String[] wordlist, String[] queries) {
          Set<String> s = new HashSet<>();
          Map<String, String> low = new HashMap<>();
          Map<String, String> pat = new HashMap<>();
          for (String w : wordlist) {
              s.add(w);
              String t = w.toLowerCase();
              low.putIfAbsent(t, w);
              pat.putIfAbsent(f(t), w);
          }
          int m = queries.length;
          String[] ans = new String[m];
          for (int i = 0; i < m; ++i) {
              String q = queries[i];
              if (s.contains(q)) {
                  ans[i] = q;
                  continue;
              }
              q = q.toLowerCase();
              if (low.containsKey(q)) {
                  ans[i] = low.get(q);
                  continue;
              }
              q = f(q);
              if (pat.containsKey(q)) {
                  ans[i] = pat.get(q);
                  continue;
              }
              ans[i] = "";
          }
          return ans;
      }
  
      private String f(String w) {
          char[] cs = w.toCharArray();
          for (int i = 0; i < cs.length; ++i) {
              char c = cs[i];
              if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                  cs[i] = '*';
              }
          }
          return String.valueOf(cs);
      }
  }
  

• 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;
      }
  };
  

• 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
  
  

• 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