Leetcode-916. Word Subsets-(Medium)

一、问题描述

We are given two arrays A and B of words. Each word is a string of lowercase letters.

Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, "wrr" is a subset of "warrior", but is not a subset of "world".

Now say a word a from A is universal if for every b in B, b is a subset of a.

Return a list of all universal words in A. You can return the words in any order.

Example 1:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]

Example 3:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]

Example 4:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]

Example 5:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]

Note:

1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i] and B[i] consist only of lowercase letters.
All words in A[i] are unique: there isn't i != j with A[i] == A[j].

　　解释：　　给定字符串数组B，如果B中的每个元素串中的每个字符都在一个字符串中（计算重复）；那么说明这个字符串符合条件　　输入两个字符串数组，A、B；B为模式字符串数组；判断A中的多少个字符串符合预期？二、解答　　

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;


bool isUniversal(string& word, std::map chr_map)
{
    for(auto c:word){
        if(chr_map.find(c) != chr_map.end())
            chr_map[c] -= 1;
    }
    
    std::map::iterator it = chr_map.begin();
    while (it != chr_map.end()) {
        if((it->second) > 0)
            return false;
        it++;
    }
    
    return true;
}

class Solution {
public:
    vector wordSubsets(vector& A, vector& B) {
        std::map chr_map;
        std::vector result;
        for(auto word:B){
            std::map chr_temp_map;
            for(auto c:word){
                chr_temp_map[c] += 1;
            }
            for (auto& kv : chr_temp_map) {
                chr_map[kv.first] = std::max(kv.second, chr_map[kv.first]);
            }
        }
        
        for(auto w: A){
            if(isUniversal(w, chr_map))
            {
                result.push_back(w);
            }
        }
        return result;
    }
};



void test()
{
    std::map chr_map;
    std::vector result{"abc","bcd","cde"};
    for(auto word:result){
        for(auto c:word){
            chr_map[c] += 1;
            cout< chr_map_copy(chr_map);
    
}


int main(int argc, const char * argv[]) {
    // insert code here...
//    test();
    Solution s;
    vector A{"amazon","apple","facebook","google","leetcode"};
    vector B{"lo","eo"};
    s.wordSubsets(A, B);
    
    return 0;
}

三、总结

　　这道题目没有特殊，主要是理解题意。

　　用到std:: map，for 遍历 c++11的语法

　　编译需要添加 -std=c++11 参数

算法相关

Leetcode-916. Word Subsets-(Medium)

相关

标签