288単語の唯一の略語

9383 ワード

タイトルの説明:単語の略語はこのようなフォーマットに従う必要があります.以下に、略語の例を示します.
a)it-->it(省略なし)
 1
 ↓

b) d|o|g --> d1g
          1    1  1
 1---5----0----5--8
 ↓   ↓    ↓    ↓  ↓    

c) i|nternationalizatio|n --> i18n
          1
 1---5----0
 ↓   ↓    ↓

d)l|ocalizatio|n-->l 10 n単語の略語が辞書の中で唯一であるかどうかを判断してください.単語の略語が以下のいずれかの条件を満たす場合、その単語の略語は唯一であると考えられる:辞書dictionaryには他の単語の略語がその単語wordの略語と同じではない.辞書dictionaryのすべての略語は、その単語wordの略語と同じ単語がwordと同じです.
例1:入力:[ValidWordAbbr],[isUnique],[isUnique],[isUnique],[isUnique][deer],[door],[cake],[card],[dear],[cart],[cane],[make]出力:[null,false,true,false,true]
解釈:ValidWordAbbr validWordAbbr=new ValidWordAbbr(["deer","door","cake","card");validWordAbbr.isUnique(“dear”);//return False validWordAbbr.isUnique(“cart”);//return True validWordAbbr.isUnique(“cane”);//return False validWordAbbr.isUnique(“make”);//return True
ヒント:各単語は小文字のみで構成されます
方法1:主な考え方:(1)与えられた辞書の文字列を先に略語し、unordered_mapを用いて統計する.(2)与えられた文字列に対して、まず略語し、その後、略語が辞書のマッピングmapに存在するかどうかを探し、存在しない場合はtrueを直接返し、存在する場合は、対応する文字列の中で文字列がすべての単語と一致しているかどうかを判断し、一致しない場合はfalseを返し、完全に一致している場合はtrueを返す.
class ValidWordAbbr {
     
public:
    unordered_map<string,vector<string>> mp;
    ValidWordAbbr(vector<string>& dictionary) {
     
    	//            
        for(string& str:dictionary){
     
            string tmp;
            if(str.size()>2){
     
                tmp=str.substr(0,1)+to_string(str.size()-2)+str.substr(str.size()-1,1);
            }
            else{
     
                tmp=str;
            }
            mp[tmp].push_back(str);
        }
    }
    
    bool isUnique(string word) {
     
        string tmp;
        //           
        if(word.size()>2){
     
            tmp=word.substr(0,1)+to_string(word.size()-2)+word.substr(word.size()-1,1);
        }
        else{
     
            tmp=word;
        }
        //           
        if(mp.count(tmp)){
     
            for(int i=0;i<mp[tmp].size();++i){
     
                if(word!=mp[tmp][i]){
     
                    return false;
                }
            }
        }
        return true;
    }
};

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr* obj = new ValidWordAbbr(dictionary);
 * bool param_1 = obj->isUnique(word);
 */