솔루션: 모음 맞춤법 검사기

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #966(중간): 모음 맞춤법 검사기

설명:

(이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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

제약:

• 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 Description || 코드: JavaScript | Python | Java | C++ )

이 문제는 난이도를 높이는 몇 단계로 나눌 수 있습니다. 첫 번째 단계는 쿼리 목록(Q)에 있는 단어가 단어 목록(W)에 존재하는지 확인하는 것입니다. 이를 위해 가장 단순한 형태의 값 조회 데이터 구조인 Set을 사용할 수 있습니다.

다음으로, 각 쿼리가 W에서 대소문자를 구분하지 않는 일치가 있는지 확인해야 합니다. 대소문자를 구분하지 않는 일치의 경우 가장 쉬운 방법은 비교하기 전에 두 용어를 모두 소문자(또는 대문자)로 사용하는 것입니다. 이 경우 하나의 용어를 일치시키고 다른 용어를 반환하기를 원하기 때문에 Map 데이터 구조를 사용해야 합니다. 여기서 키는 소문자 용어이고 값은 일치하는 단어입니다.

그러나 두 단어가 동일한 소문자 형식을 가질 수 있으므로 여기서 문제가 발생합니다. 규칙에 따라 W에서 처음 나타나는 것을 선호하므로 W를 통해 반복하고 기존 항목을 덮어쓰지 않는지 반복적으로 확인할 수 있습니다. 또는 W를 거꾸로 반복하고 자동으로 덮어쓸 수 있습니다 항목. 이렇게 하면 첫 번째 항목이 "고정"되는 항목이 됩니다.

세 번째 검사에서는 모음을 제외한 단어를 일치시켜야 합니다. 부분적으로만 문자열을 선택적으로 일치시켜야 할 때 가장 쉬운 방법은 마스크를 사용하는 것입니다. 이 경우 정규식을 사용하여 모든 모음 발생을 "#"과 같은 문자 마스크로 바꿀 수 있습니다. 예를 들어 "꼬리"와 "도구"가 두 용어에 문자 마스크를 적용하고 "t##l"== "t##l"임을 확인하여 "꼬리"와 "도구"가 일치하는지 확인할 수 있습니다.

이것은 또 다른 맵 구조를 요구합니다. 중복이 없기 때문에 기술적으로 이전 맵을 재사용할 수 있지만 두 개의 별도의 작은 맵을 탐색하는 것이 일반적으로 하나의 큰 맵보다 더 효율적입니다. 이 맵에 대해 W를 통해 역방향으로 반복하기를 원할 것이므로 다른 맵과 동시에 이를 수행할 수도 있습니다.

그런 다음 Q를 반복하고 올바른 순서로 일치하는 항목을 확인할 수 있습니다. 일반적으로 쿼리 목록의 경우와 마찬가지로 공간 복잡성을 줄이기 위해 Q의 쿼리를 결과로 바꿀 수 있습니다.

그런 다음 완료되면 Q를 반환합니다.

구현:

Javascript는 논리적 OR 연결을 사용하여 Q에서 적절한 결과의 할당을 단축할 수 있습니다.

Regex는 Java 및 C++에서 훨씬 느리므로 도우미 함수를 사용하여 동일한 작업을 수행할 수 있습니다.

C++에는 단어를 소문자로 변환하는 도우미도 필요합니다.

자바스크립트 코드:

(이동: Problem Description || Solution Idea )

const regex = /[aeiou]/g
var spellchecker = function(W, Q) {
    let orig = new Set(W), lower = new Map(), mask = new Map()
    for (let i = W.length - 1; ~i; i--) {
        let word = W[i], wlow = word.toLowerCase()
        lower.set(wlow, word)
        mask.set(wlow.replace(regex, "*"), word)
    }
    for (let i in Q) {
        let query = Q[i], qlow = query.toLowerCase(),
            qmask = qlow.replace(regex, "*")
        if (orig.has(query)) continue
        else Q[i] = lower.get(qlow) || mask.get(qmask) || ""
    }
    return Q
};

파이썬 코드:

(이동: Problem Description || Solution Idea )

class Solution:
    def spellchecker(self, W: List[str], Q: List[str]) -> List[str]:
        orig, lcase, mask = set(W), defaultdict(), defaultdict()
        regex = r'[aeiou]'
        for i in range(len(W)-1,-1,-1):
            word = W[i]
            wlow = word.lower()
            lcase[wlow] = word
            mask[re.sub(regex, '*', wlow)] = word
        for i in range(len(Q)):
            query = Q[i]
            qlow = query.lower()
            qmask = re.sub(regex, '*', qlow)
            if query in orig: continue
            elif qlow in lcase: Q[i] = lcase[qlow]
            elif qmask in mask: Q[i] = mask[qmask]
            else: Q[i] = ""
        return Q

자바 코드:

(이동: Problem Description || Solution Idea )

class Solution {
    public String[] spellchecker(String[] W, String[] Q) {
        Set<String> orig = new HashSet<>(Arrays.asList(W));
        Map<String, String> lower = new HashMap<>(), mask = new HashMap<>();
        for (int i = W.length - 1; i >= 0; i--) {
            String word = W[i], wlow = word.toLowerCase();
            lower.put(wlow, word);
            mask.put(vmask(wlow), word);
        }
        for (int i = 0; i < Q.length; i++) {
            String query = Q[i], qlow = query.toLowerCase(),
                qmask = vmask(qlow);
            if (orig.contains(query)) continue;
            else if (lower.containsKey(qlow)) Q[i] = lower.get(qlow);
            else if (mask.containsKey(qmask)) Q[i] = mask.get(qmask);
            else Q[i] = "";
        }
        return Q;
    }
    public String vmask(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') c = '*';
            sb.append(c);
        }
        return sb.toString();
    }
}

C++ 코드:

(이동: Problem Description || Solution Idea )

class Solution {
public:
    vector<string> spellchecker(vector<string>& W, vector<string>& Q) {
        set<string> orig (W.begin(), W.end());
        unordered_map<string, string> lower, mask;
        for (int i = W.size() - 1; ~i; i--) {
            string word = W[i], wlow = lcase(word);
            lower[wlow] = word, mask[vmask(wlow)] = word;
        }
        for (string &query : Q) {
            string qlow = lcase(query), qmask = vmask(qlow);
            if (orig.count(query)) continue;
            else if (lower.count(qlow)) query = lower[qlow];
            else if (mask.count(qmask)) query = mask[qmask];
            else query = "";
        }
        return Q;
    }
    static string vmask(string str) {
        for (char &c : str)
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
                c = '*';
        return str;
    }
    static string lcase(string str) {
        for (char &c : str) c = tolower(c);
        return str;
    }
};