Word Lader ใน C++

สมมติว่าเรามีคำสองคำ (beginWord และ endWord) และเรามีรายการคำศัพท์ในพจนานุกรม ให้ค้นหาความยาวของลำดับการแปลงที่สั้นที่สุดจาก beginWord ถึง endWord เช่นนั้น -

• แปลงได้ครั้งละหนึ่งตัวอักษรเท่านั้น

• ในแต่ละคำที่แปลงแล้วจะต้องมีอยู่ในรายการคำศัพท์ BeginWord ไม่ใช่คำที่ถูกแปลง

เราต้องจำไว้ว่า -

• คืนค่า 0 เมื่อไม่มีลำดับการเปลี่ยนแปลงดังกล่าว

• ทุกคำมีความยาวเท่ากัน

• ทุกคำมีเฉพาะตัวพิมพ์เล็กเท่านั้น

• เราไม่สามารถถือว่าไม่ซ้ำกันในรายการคำ

ดังนั้นหากอินพุตมีลักษณะดังนี้:beginWord ="hit", endWord ="cog" และ wordlist =["hot", "dot", "dog", "lot", "log", "cog"]

จากนั้นผลลัพธ์จะเป็น 5 เนื่องจากการแปลงที่สั้นที่สุดหนึ่งครั้งคือ → hot → dot → dog → cog

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

• กำหนดวิธีการที่เรียกว่า putStar ซึ่งจะใช้ j และ string s สิ่งนี้จะทำงานดังนี้ −

• temp :=สตริงว่าง

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาด s – 1

  • ถ้า i =j ให้อัปเดต temp โดยเชื่อม “*” กับมัน มิฉะนั้น ให้อัปเดต temp โดยการต่อ s[i] กับ temp

• ในวิธีการหลักจะใช้สตริง b สตริง e และรายการคำ w ซึ่งจะทำงานดังนี้ -

• ถ้า e ไม่อยู่ใน w หรือ b ว่างเปล่า หรือ e ว่างเปล่า หรือ w ว่างเปล่า ให้คืนค่า 0

• กำหนดแผนที่ m สำหรับคีย์ประเภทสตริงและค่าประเภทอาร์เรย์

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ w

  • x :=w[i]

  • สำหรับ j :=0 ถึงขนาด x

    • อินเตอร์ :=putStar(j, x)

    • แทรก x ลงใน m[inter]

• กำหนดคิว q ใส่คู่ (b, 1) ลงใน q

• ทำแผนที่ชื่อเยี่ยมชม

• ในขณะที่ q ไม่ว่างเปล่า

  • s :=คู่หน้าจาก q ลบองค์ประกอบด้านหน้าจาก q

  • x :=องค์ประกอบแรกของคู่ s, l :=องค์ประกอบที่สองของคู่ s

  • สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ x

    • temp :=putStar(i, x)

    • สำหรับ j ในช่วง 0 ถึงขนาด m[temp]

      • aa :=m[temp, j]

      • ถ้า aa เหมือนกับ e ให้คืนค่า l + 1

      • หากไม่ได้ตั้งค่า visit[aa] ให้ใส่คู่ (aa, l + 1) และตั้งค่า visit[aa] =1

• ระดับ :=0

• คืนค่า 0

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string putStar(int j, string s){
      string temp = "";
      for(int i = 0; i < s.size(); i++){
         if(i == j)temp += "*";
         else temp += s[i];
      }
      return temp;
   }
   int ladderLength(string b, string e, vector<string>& w) {
      if(find(w.begin(), w.end(), e) == w.end() || !b.size() || !e.size() || !w.size())return 0;
      map < string , vector <string> > m;
      for(int i = 0; i < w.size(); i++){
         string x = w[i];
         for(int j = 0; j < x.size(); j++){
            string inter = putStar(j,x);
            m[inter].push_back(x);
         }
      }
      queue < pair <string, int> > q;
      q.push({b, 1});
      map <string, int> visited;
      while(!q.empty()){
         pair < string, int > s = q.front();
         q.pop();
         string x = s.first;
         int l = s.second;
         for(int i = 0; i < x.size(); i++){
            string temp = putStar(i ,x);
            for(int j = 0; j < m[temp].size(); j++){
               string aa = m[temp][j];
               if(aa == e)return l+1;
               if(!visited[aa]){
                  q.push({aa, l+1});
                  visited[aa] = 1;
               }
            }
         }
      }
      int level = 0;
      return 0;
   }
};
main(){
   vector<string> v = {"hot","dot","dog","lot","log","cog"};
   Solution ob;
   cout << (ob.ladderLength("hit", "cog", v));
}

อินพุต

"hit"
"cog"
["hot","dot","dog","lot","log","cog"]

ผลลัพธ์

5