Thang từ trong C ++

Giả sử chúng ta có hai từ (beginWord và endWord) và chúng ta có danh sách từ trong từ điển, hãy tìm độ dài của chuỗi chuyển đổi ngắn nhất từ beginWord sang endWord, sao cho -

Mỗi lần chỉ có thể chuyển đổi một chữ cái.
Trong mỗi từ được biến đổi phải tồn tại trong danh sách từ. BeginWord không phải là một từ đã được biến đổi.

Chúng tôi phải ghi nhớ rằng -

Trả về 0 khi không có chuỗi thay đổi như vậy.
Tất cả các từ đều có cùng độ dài.
Tất cả các từ chỉ chứa các ký tự viết thường.
Chúng tôi có thể cho rằng không có bản nào trùng lặp trong danh sách từ.

Vì vậy, nếu đầu vào là:beginWord ="hit", endWord ="cog" và wordlist =["hot", "dot", "dog", "lot", "log", "cog"]

Sau đó, đầu ra sẽ là 5, khi một phép biến đổi ngắn nhất được nhấn → nóng → chấm → chó → bánh răng

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

Định nghĩa một phương thức gọi là putStar, phương thức này sẽ lấy j và chuỗi s. Điều này sẽ hoạt động như sau -
temp:=chuỗi trống
cho tôi trong phạm vi từ 0 đến kích thước của s-1
- nếu i =j, thì cập nhật tạm thời bằng cách nối “*” với nó, nếu không thì cập nhật tạm thời bằng cách nối s [i] với temp.
trong phương thức chính, nó sẽ lấy chuỗi b, chuỗi e và danh sách các từ w, điều này sẽ hoạt động như -
nếu e không có trong w, hoặc b trống, e trống hoặc w trống, thì trả về 0
xác định một bản đồ m cho khóa kiểu chuỗi và giá trị kiểu mảng.
cho tôi trong phạm vi từ 0 đến kích thước của w
- x:=w [i]
- for j:=0 to size of x
  - inter:=putStar (j, x)
  - chèn x vào m [inter]
Xác định hàng đợi q, chèn một cặp (b, 1) vào q
tạo một bản đồ được gọi là đã thăm
trong khi q không trống
- s:=cặp phía trước từ q, xóa phần tử phía trước khỏi q
- x:=phần tử đầu tiên của cặp s, l:=phần tử thứ hai của cặp s
- cho tôi trong phạm vi từ 0 đến kích thước của x
  - temp:=putStar (i, x)
  - cho j trong phạm vi 0 đến kích thước của m [temp]
    - aa:=m [temp, j]
    - nếu aa giống với e, thì trả về l + 1
    - nếu đã truy cập [aa] không được đặt, thì hãy chèn cặp (aa, l + 1) và đặt đã truy cập [aa] =1
cấp:=0
trả về 0

Ví dụ

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

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

Đầu vào

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

Thang từ trong C ++

Ví dụ

Đầu vào

Đầu ra