สติ๊กเกอร์สะกดคำใน C ++

สมมติว่าเรามีสติกเกอร์ประเภทต่างๆ N ในสติกเกอร์แต่ละประเภทจะมีคำภาษาอังกฤษตัวพิมพ์เล็กอยู่ เราต้องการสะกดสตริงเป้าหมายที่กำหนดโดยการตัดตัวอักษรแต่ละตัวจากคอลเล็กชันสติกเกอร์ของเราและจัดเรียงใหม่ เราสามารถใช้สติกเกอร์แต่ละอันได้มากกว่าหนึ่งครั้งหากต้องการ และเรามีสติกเกอร์แต่ละแบบจำนวนไม่จำกัด

เราต้องหาจำนวนสติกเกอร์ขั้นต่ำที่เราต้องใช้เพื่อสะกดเป้าหมายหรือไม่? หากภารกิจนี้เป็นไปไม่ได้ ให้คืนค่า -1

ดังนั้นหากอินพุตเป็นเหมือน ["dog", "sentence", "antenna"] และเป้าหมายคือ "dance" คำตอบจะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของเป้าหมาย
• N :=เลื่อน 1 ไปทางซ้าย n ครั้ง
• กำหนดอาร์เรย์ dp ขนาด N เริ่มต้นด้วย inf
• dp[0] :=0
• สำหรับการเริ่มต้น i :=0 เมื่อ i
• ถ้า dp[i] เหมือนกับ inf แล้ว −
  • ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
• สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของสติกเกอร์ อัปเดต (เพิ่ม j โดย 1) ทำ −
  • s :=สติกเกอร์[j]
  • x :=ฉัน
  • สำหรับการเริ่มต้น k :=0 เมื่อ k <ขนาดของ s อัปเดต (เพิ่ม k ขึ้น 1) ทำ −
    • z :=s[k]
    • สำหรับการเริ่มต้น l :=0 เมื่อ l <ขนาดของเป้าหมาย อัปเดต (เพิ่ม l ขึ้น 1) ทำ −
      • ถ้าเป้าหมาย[l] เหมือนกับ z และ (ขยับขวา x, l บิต ) และ 1) เหมือนกับ 0 ดังนั้น −
        • x :=x OR (เลื่อน 1 ไปทางซ้าย l บิต)
        • ออกมาจากวงจร
  • 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