Leetcode 748. 最短補全詞(今天結束)

給你一個字元串 licensePlate 和一個字元串數組 words ，請你找出 words 中的 最短補全詞 。

補全詞 是一個包含 licensePlate 中所有字母的單詞。忽略 licensePlate 中的 數字和空格 。不區分大小寫。如果某個字母在 licensePlate 中出現不止一次，那麼該字母在補全詞中的出現次數應當一緻或者更多。

例如：licensePlate = "aBc 12c"，那麼它的補全詞應當包含字母 'a'、'b' （忽略大寫）和兩個 'c' 。可能的 補全詞 有 "abccdef"、"caaacab" 以及 "cbca" 。

請傳回 words 中的 最短補全詞 。題目資料保證一定存在一個最短補全詞。當有多個單詞都符合最短補全詞的比對條件時取 words 中 第一個 出現的那個。

示例 1：

輸入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
輸出："steps"
解釋：最短補全詞應該包括 "s"、"p"、"s"（忽略大小寫） 以及 "t"。
"step" 包含 "t"、"p"，但隻包含一個 "s"，是以它不符合條件。
"steps" 包含 "t"、"p" 和兩個 "s"。
"stripe" 缺一個 "s"。
"stepple" 缺一個 "s"。
是以，"steps" 是唯一一個包含所有字母的單詞，也是本例的答案。      

輸入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
輸出："pest"
解釋：licensePlate 隻包含字母 "s" 。所有的單詞都包含字母 "s" ，其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest" ，因為它是三個單詞中在 words 裡最靠前的那個。      

• 1 <= licensePlate.length <= 7
• licensePlate 由數字、大小寫字母或空格 ' ' 組成
• 1 <= words.length <= 1000
• 1 <= words[i].length <= 15
• words[i] 由小寫英文字母組成

class Solution {
public:
    typedef struct
    {
        int index;
        string str;
    }para;
    
    static bool cmp(const para&s1,const para &s2)
    {
        if(s1.str.length()==s2.str.length())
        {
            return s1.index<s2.index;
        }
        return s1.str.length()<s2.str.length();
    }
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        map<char,int>mymap;
        
        
        vector<para>res;
        for(int i=0;i<licensePlate.size();i++)
        {
            
            if(tolower(licensePlate[i])>='a'&&tolower(licensePlate[i]<='z'))
            {
                mymap[tolower( licensePlate[i])]++;
            }
            
        }
        
        for(int i=0;i<words.size();i++)
        {
            map<char,int>temp;
            
            for(int j=0;j<words[i].length();j++)
            {
                temp[tolower(words[i][j])]++;
            }
            map<char,int>::iterator it;
            
            bool flag=false;
            for(it=mymap.begin();it!=mymap.end();++it)
            {
                if(temp[it->first]<it->second)
                {
                    flag=true;
                    break;
                }
            }
            if(!flag)
            {
                para p;
                p.index=i;
                p.str=words[i];
                res.push_back(p);
            }
            
        }
        
        sort(res.begin(),res.end(),cmp);
        
        cout<<res[0].str<<endl;
        return res[0].str;
    }
    
    
};