C++의 각 퍼즐에 유효한 단어 수

퍼즐 문자열이 있다고 가정하고 다음 조건이 모두 유효한 경우 단어는 유효합니다 -

• 단어는 퍼즐의 첫 글자를 포함합니다.

• 단어의 각 문자에 대해 해당 문자는 퍼즐에 있습니다.

예를 들어 퍼즐이 "abcdefg"와 같으면 유효한 단어가 "얼굴", "양배추" 등이라고 가정합니다. 그러나 일부 유효하지 않은 단어는 "a"가 없기 때문에 "beefed"이고 퍼즐에 없는 "based"가 있기 때문에 "based"입니다.

답 목록을 찾아야 합니다. 여기서 답[i]는 퍼즐 퍼즐[i]과 관련하여 유효한 주어진 단어 목록 단어의 단어 수입니다.

따라서 입력이 단어 =["aaaa","asas","able","ability","actt","actor","access"], 퍼즐 =["aboveyz","abrodyz", "abslute","absoryz","actresz","gaswxyz"], 출력은 "aboveyz":"aaaa", 하나의 유효한 단어로 [1,1,3,2,4,0]이 됩니다. "abrodyz"에 유효한 단어:"aaaa", "abslute"에 유효한 세 단어:"aaaa", "asas", "able", "absoryz"에 유효한 두 단어:"aaaa", "asas", 유효한 네 단어 "actresz":"aaaa", "asas", "actt", "access" 및 "gaswxyz"에 유효한 단어가 없습니다. 목록에 'g' 문자가 포함되어 있지 않기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• getMask() 함수를 정의하면 s가 필요합니다.

• 마스크 :=0

• initialize i :=0의 경우, i

  • 마스크 :=마스크 OR 2^(s[i] - 'a'의 ASCII)

• 리턴 마스크

• 주요 방법에서 다음을 수행하십시오 -

• 배열 정의

• 하나의 맵 정의

• initialize i :=0의 경우, i

  • 단어 :=w[i]

  • 마스크 :=0

  • for initialize j :=0, j <단어 크기일 때 업데이트(j를 1만큼 증가), do−

    • 마스크 :=마스크 또는 getMask(w[i])

  • (m[마스크]를 1씩 증가)

• initialize i :=0의 경우, i

  • 단어 :=p[i]

  • 마스크 :=getMask(단어)

  • 첫 번째 :=2^(단어[0] - 'a'의 ASCII)

  • 현재 :=마스크

  • 온도 :=0

  • 현재> 0일 때 −

    • current &first가 0이 아닌 경우 -

      • 현재 :=(현재 - 1) AND 마스크

  • ans의 끝에 temp 삽입

• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
   public:
   lli getMask(string s){
      lli mask = 0;
      for(int i =0;i<s.size();i++){
         mask|= 1<<(s[i]-'a');
      }
      return mask;
   }
   vector<int> findNumOfValidWords(vector<string>& w, vector<string>& p) {
      vector <int> ans;
      map <lli, lli > m;
      for(int i =0;i<w.size();i++){
         string word = w[i];
         lli mask = 0;
         for(int j =0;j<word.size();j++){
            mask|= getMask(w[i]);
         }
         m[mask]++;
      }
      for(int i = 0; i<p.size();i++){
         string word = p[i];
         lli mask = getMask(word);
         lli first = 1<<(word[0]-'a');
         lli current = mask;
         lli temp = 0;
         while(current>0){
            if(current & first)temp+=m[current];
            current = (current-1)&mask;
         }
         ans.push_back(temp);
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<string> v = {"aaaa","asas","able","ability","actt","actor","access"};
   vector<string> v1 = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
   print_vector(ob.findNumOfValidWords(v,v1));
}

입력

{"aaaa","asas","able","ability","actt","actor","access"},
{"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"}

출력

[1, 1, 3, 2, 4, 0, ]