966. Vowel Spellchecker

https://leetcode.com/problems/vowel-spellchecker/

Vowel Spellchecker - LeetCode

 

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.

 

 

---

문제가 굉장히 까다롭고 해석도 어렵다.

 

결론적으로 말하면 queries에서 받은 문자열을 wordlist로 대체 가능하냐는것이다.

 

대체의 기준은

1. 모든 대문자를 소문자로 변경한 결과가 wordlist에 있는가
2. a, e, i, o, u 5개의 문자를 서로간에 변경이 가능할때에 wordlist에 있는가

풀이방법은 도무지 감이 안잡혔지만 topic에 hash table을 써라는 것을 보고 힌트를 얻었다.

 

queries에 있는 문자열와 호환이 가능한 문자열을 key로 삼아 해쉬에서 탐색하면 되는것이다.

 

가령

wordlist 에 yellow 가 있고 queries에 YellOw가 있으면 쿼리의 문자열을 소문자로 바꾼 yellow를 통해 검색한 결과를 얻을 수 있다.

 

그리고

wordlist 에 ae 가 있고 queries에 UU가 있으면 쿼리의 문자열을 소문자로 바꾼 ae를 통해 검색한 결과를 얻을 수 있다.

 

 

그러기 위해선 우리는 3가지 해쉬를 만들어야 한다.

org : wordlist의 문자열을 있는 그대로 key삼아 검색하는 hash

cap : wordlist의 문자열에서 대문자를 소문자로 바꾼 문자열을 key 삼아 검색하는 hash

vowel : wordlist의 문자열에서 a, e, i, o, u를 #으로 바꾼 문자열을 key 삼아 검색하는 hash

 

3가지 해쉬를 모두다 정의 해준 후엔

 

queries에 있는 문자열 또한 필요에 따라 규칙에 맞게 변형 시켜서 3가지 hash에서 검색하도록 한다.

 

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
string dummy = "";
 
class HashListNode {
public:
    string value;
    string key;
    HashListNode *pPrev, *pNext;
 
    HashListNode() {
        value = -1;
        pPrev = 0;
        pNext = 0;
    }
};
 
 
HashListNode hashListNodePool[500000];
int hashListNodePoolIndex;
 
void HashListNodePoolInit() {
    hashListNodePoolIndex = 0;
}
 
 
HashListNode* NewHashListNode() {
    HashListNode* newNode;
    newNode = &hashListNodePool[hashListNodePoolIndex];
    hashListNodePoolIndex++;
 
    newNode->pNext = 0;
    newNode->pPrev = 0;
    return newNode;
}
 
 
class HashList {
public:
    int cnt;
    HashListNode *front, *back;
 
    void Init() {
        cnt = 0;
        front = NewHashListNode();
        back = NewHashListNode();
 
        front->pNext = back;
        back->pPrev = front;
    }
 
 
 
    void PushBack(string &value, string &key) {
        HashListNode *newNode = NewHashListNode();
        newNode->value = value;
        newNode->key = key;
 
 
        HashListNode *lastNode = back->pPrev;
        lastNode->pNext = newNode;
        back->pPrev = newNode;
 
        newNode->pPrev = lastNode;
        newNode->pNext = back;
        cnt++;
    }
 
 
    bool Insert(string &newValue, string &newKey) {
        //중복 여부 조사    
        PushBack(newValue, newKey);
 
        return true;
    }
 
 
    HashListNode* Erase(HashListNode *deleteNode) {
        HashListNode *prevNode = deleteNode->pPrev;
        HashListNode *nextNode = deleteNode->pNext;
 
        prevNode->pNext = nextNode;
        nextNode->pPrev = prevNode;
 
        delete deleteNode;
        cnt--;
 
        return nextNode;
    }
 
    string& Find(string &key) {
        HashListNode *it = front->pNext;
 
        for (it = front->pNext; it != back; it = it->pNext) {
            if (it->key == key)
                break;
        }
 
        if (it != back)
            return it->value;
        else
            return dummy;
    }
};
 
 
class Hash {
public:
    int cnt;
    HashList hashTable[5017];
 
    void Init() {
        cnt = 0;
 
        for (int i = 0; i < 5017; i++)
            hashTable[i].Init();
    }
 
    int HashFunction(string &key) {
 
        char c;
        int ret = 0;
        for (int i = 0; i < key.size(); i++) {
            c = key[i];
 
            //ret = ((ret * 31) + c - 'a') % 1000;
            if(c >= 'a' && c <= 'z')
                ret = ((ret * 31) + c - 'a') % 5017;
            else if(c >= 'A' && c <= 'Z')
                ret = ((ret * 31) + c - 'A') % 5017;
            else if(c == '#')
                ret = ((ret * 31) + 31) % 5017;
 
        }
        return ret;
    }
 
 
    string Find(string &key) {
        int address = HashFunction(key);
 
        string &ret = hashTable[address].Find(key);
 
        return ret;
    }
 
    bool Insert(string &key, string &value) {
        //이미있는지 점검과 삽입을 동시에 한다
        //삽입 도중에 이미 있음이 발견되면 바로 false 반환
 
        int address = HashFunction(key);
 
        bool ret = hashTable[address].Insert(value, key);
        return ret;
    }
 
};
 
 
string ToLower(string &str) {
    string ret;
    int diff = 'A' - 'a';
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] >= 'A' && str[i] <= 'Z')
            ret.push_back(str[i] - diff);
        else
            ret.push_back(str[i]);
    }
    return ret;
}
 
string ToVowel(string &str) {
    string ret;
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u')
            ret.push_back('#');
        else
            ret.push_back(str[i]);
    }
 
    return ret;
}
 
 
class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        Hash org, cap, vowel;
        string tmp;
 
        HashListNodePoolInit();
        org.Init(); cap.Init(); vowel.Init();
 
        //cap에 wordlist 내의 값들을 모두다 집어 넣는다
        //key는 모든 문자열을 소문자로 바꾼 값이다.
 
        //vowel에 queries 내의 문자열을 모두 넣는다
        //key는 a, e, i ,o ,u 를 #으로 바꾼 문자열이다.
        for (int i = 0; i < wordlist.size(); i++) {
            org.Insert(wordlist[i], wordlist[i]);
 
            tmp = ToLower(wordlist[i]);
            cap.Insert(tmp, wordlist[i]);
 
            tmp = ToVowel(tmp);
            vowel.Insert(tmp, wordlist[i]);
        }
 
        string ret, key;
        //이제 queries의 값을 변환 가능한지 점검한다.
        for (int i = 0; i < queries.size(); i++) {
            //아무것도 바꿀 필요가 없을 경우
            ret = org.Find(queries[i]);
 
            if (ret != dummy)
                continue;
 
            //소문자로 바꾼 결과가 cap에 있을 경우
            key = ToLower(queries[i]);
            ret = cap.Find(key);
 
            if (ret != dummy) {
                queries[i] = ret;
                continue;
            }
 
            //a,e,i,o,u 로 바꾼 결과가 vowel에 있을 경우
            key = ToVowel(key);
            ret = vowel.Find(key);
 
            if (ret != dummy) {
                queries[i] = ret;
                continue;
            }
 
            //아무것도 해당사항이 없으면 문자열을 비운다.
            queries[i] = "";
        }
 
        return queries;
    }
};
 
 
 
int main(void) {
    int N, M;
    cin >> N >> M;
 
    string str;
    vector<string> wordlist, queries;
 
 
    for (int i = 0; i < N; i++) {
        cin >> str;
        wordlist.push_back(str);
    }
 
    for (int i = 0; i < M; i++) {
        cin >> str;
        queries.push_back(str);
    }
 
    Solution sol;
    vector<string> ret = sol.spellchecker(wordlist, queries);
 
    for (int i = 0; i < ret.size(); i++) {
        cout << ret[i] << endl;
    }
 
    return 0;
}