Hình dán để đánh vần Word trong C ++

Giả sử chúng ta có N loại nhãn dán khác nhau. Trong mỗi loại nhãn dán có một từ tiếng Anh viết thường trên đó. Chúng tôi muốn đánh vần chuỗi mục tiêu đã cho bằng cách cắt các chữ cái riêng lẻ từ bộ sưu tập nhãn dán của chúng tôi và sắp xếp lại chúng. Chúng tôi có thể sử dụng mỗi hình dán nhiều lần nếu cần và chúng tôi có số lượng vô hạn cho mỗi hình dán.

Chúng ta phải tìm số lượng nhãn dán tối thiểu mà chúng ta cần để đánh vần mục tiêu? Nếu nhiệm vụ không thể thực hiện được, hãy trả về -1.

Vì vậy, nếu đầu vào là [“dog”, “question”, “anten”] và mục tiêu là “dance”, thì câu trả lời sẽ là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mục tiêu
• N:=shift 1 sang trái n lần
• Xác định một mảng dp có kích thước N khởi tạo nó bằng inf
• dp [0]:=0
• để khởi tạo i:=0, khi i
• nếu dp [i] giống với inf, thì -
  • Bỏ qua phần sau, chuyển sang phần lặp tiếp theo
• để khởi tạo j:=0, khi j
• s:=nhãn dán [j]
• x:=i
• để khởi tạo k:=0, khi k
• z:=s [k]
• để khởi tạo l:=0, khi l
• nếu target [l] giống z và (chuyển sang phải x, l bit) VÀ 1) giống 0, thì -
  • x:=x OR (dịch chuyển 1 sang trái l bit)
  • Thoát khỏi vòng lặp

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

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

Đầu ra

3