【leetcode】966. Vowel Spellchecker

题目如下：

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.

解题思路：题目给定了优先级关系，首先是精确匹配，然后是忽略大小写匹配，再接下来是忽略元音匹配。我的思路是用三个字典，第一个字典保存wordlist中所有元素，第二个字典保存wordlist把所有单词转换成小写后的新单词，第三个字典保存wordlist中的把所有单词中元音都替换成'a'的新单词。匹配queries中的单词也是一样的顺序，首先是精确匹配，然后忽略大小写，最后是元音都替换成'a'。

代码如下：

class Solution(object):

    def replaceVowel(self,v):

        newv = ''

        v = v.lower()

        vowel = ['a', 'e', 'i', 'o', 'u']

        for j in v:

            if j in vowel:

                newv += 'a'

            else:

                newv += j

        return newv

    def spellchecker(self, wordlist, queries):

        """

        :type wordlist: List[str]

        :type queries: List[str]

        :rtype: List[str]

        """

        dic = {}

        dic_case = {}

        dic_vowel = {}

        for i,v in enumerate(wordlist):

            if v not in dic:

                dic[v] = i

            if v.lower() not in dic_case:

                dic_case[v.lower()] = i

            newv = self.replaceVowel(v)

            if newv not in dic_vowel:

                dic_vowel[newv] = i

        res = []

        for i in queries:

            if i in dic:

                res.append(wordlist[dic[i]])

            elif i.lower() in dic_case:

                res.append(wordlist[dic_case[i.lower()]])

            elif self.replaceVowel(i) in dic_vowel:

                res.append(wordlist[dic_vowel[self.replaceVowel(i)]])

            else:

                res.append('')

        return res

巴特西

【leetcode】966. Vowel Spellchecker

最新文章

热门文章