Thang từ (Độ dài của chuỗi ngắn nhất để đạt được một từ đích) trong C ++

Trong bài toán này, chúng ta được đưa ra một từ điển và hai từ ‘start’ và ‘target’. Nhiệm vụ của chúng tôi là tạo một chuỗi (bậc thang) từ bắt đầu công việc đến từ đích, chuỗi được tạo sao cho mỗi từ chỉ khác ký tự khác một từ và từ đó cũng phải tồn tại trong từ điển. Từ đích tồn tại trong từ điển và độ dài của tất cả các từ đều giống nhau. Chương trình sẽ trả về độ dài của đường đi ngắn nhất từ ​​đầu đến đích.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

Dictionary = {‘HEAL’, ‘HATE’, ‘HEAT’, ‘TEAT’, ‘THAT’, ‘WHAT’ , ‘HAIL’ ‘THAE’}
Start = ‘HELL’
Target = ‘THAE’

Đầu ra

6

Giải thích

HELL - HEAL - HEAT - TEAT - THAT - THAE

Để giải quyết vấn đề này, chúng tôi sẽ thực hiện tìm kiếm Breadth-first của từ điển. Bây giờ, từng bước tìm tất cả các phần tử cách ký tự trước đó một chữ cái. Và tạo một nấc thang từ đầu đến mục tiêu.

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int wordLadder(string start, string target, set<string>& dictionary) {
   if (dictionary.find(target) == dictionary.end())
   return 0;
   int level = 0, wordlength = start.size();
   queue<string> ladder;
   ladder.push(start);
   while (!ladder.empty()) {
      ++level;
      int sizeOfLadder = ladder.size();
      for (int i = 0; i < sizeOfLadder; ++i) {
         string word = ladder.front();
         ladder.pop();
         for (int pos = 0; pos < wordlength; ++pos) {
            char orig_char = word[pos];
            for (char c = 'a'; c <= 'z'; ++c) {
               word[pos] = c;
               if (word == target)
                  return level + 1;
               if (dictionary.find(word) == dictionary.end())
                  continue;
               dictionary.erase(word);
               ladder.push(word);
            }
            word[pos] = orig_char;
         }
      }
   }
   return 0;
}
int main() {
   set<string> dictionary;
   dictionary.insert("heal");
   dictionary.insert("heat");
   dictionary.insert("teat");
   dictionary.insert("that");
   dictionary.insert("what");
   dictionary.insert("thae");
   dictionary.insert("hlle");
   string start = "hell";
   string target = "thae";
   cout<<"Length of shortest chain from '"<<start<<"' to '"<<target<<"' is: "<<wordLadder(start, target, dictionary);
   return 0;
}

Đầu ra

Length of shortest chain from 'hell' to 'thae' is: 6