Leetcode-916. Word Subsets-(Medium)-白红宇

Leetcode-916. Word Subsets-(Medium)

阅读量：4549 次

发布时间：2019-06-08

本文共 2727 字，大约阅读时间需要 9 分钟。

一、问题描述

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::<string> map，for 遍历 c++11的语法

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

转载于:https://www.cnblogs.com/doudouyoutang/p/10190507.html

你可能感兴趣的文章