C++에서 단어 맞춤법 스티커

N개의 다른 유형의 스티커가 있다고 가정합니다. 스티커의 각 유형에는 소문자 영어 단어가 있습니다. 우리는 스티커 컬렉션에서 개별 문자를 잘라내어 재배열하여 지정된 대상 문자열을 철자하고 싶습니다. 필요한 경우 각 스티커를 한 번 이상 사용할 수 있으며 각 스티커의 수량은 무한합니다.

우리는 대상을 철자하는 데 필요한 최소한의 스티커를 찾아야만 합니까? 작업이 불가능한 경우 -1을 반환합니다.

따라서 입력이 ["dog", "sentence", "antenna"]이고 대상이 "dance"인 경우 답은 3

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

• n :=대상 크기
• N :=1을 왼쪽으로 n번 이동
• 크기 N의 배열 dp를 정의하고 inf로 초기화
• dp[0] :=0
• 초기화 i의 경우:=0, i
• dp[i]가 inf와 같으면 -
  • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
• j 초기화의 경우:=0, j <스티커 크기, 업데이트(j를 1만큼 증가), 수행 -
  • :=스티커[j]
  • x :=나
  • 초기화 k의 경우:=0, k
  • z :=s[k]
  • 초기화 l :=0의 경우, l <타겟의 크기일 때 업데이트(l을 1씩 증가), 수행 -
    • target[l]이 z와 동일하고 (오른쪽 시프트 x, l 비트) AND 1)이 0과 같으면 -
      • x :=x OR (왼쪽 l비트로 1 이동)
      • 루프에서 빠져나오기
• dp[x] :=dp[x] 및 dp[i] + 1의 최소값

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

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minStickers(vector<string>& stickers, string target) {
      int n = target.size();
      int N = 1 << n;
      vector <int> dp(N, INT_MAX);
      dp[0] = 0;
      for(int i = 0; i < N; i++){
         if(dp[i] == INT_MAX) continue;
         for(int j = 0; j < stickers.size(); j++){
            string s = stickers[j];
            int x = i;
            for(int k = 0; k < s.size(); k++){
               char z = s[k];
               for(int l = 0; l < target.size(); l++){
                  if(target[l] == z && ((x >> l) & 1) == 0){
                     x |= (1 << l);
                     break;
                  }
               }
            }
            dp[x] = min(dp[x], dp[i] + 1);
         }
      }
      return dp[N - 1] == INT_MAX? -1 : dp[N - 1];
   }
};
main(){
   Solution ob;
   vector<string> v = {"dog", "sentence","antenna"};
   cout << (ob.minStickers(v, "dance"));
}

입력

["dog", "sentence","antenna"]
"dance"

출력

3