이 문제에서는 사전과 '시작'과 '목표'라는 두 단어가 제공됩니다. 우리의 임무는 시작 작업에서 대상 단어까지 체인(사다리)을 생성하는 것입니다. 체인은 각 단어가 다른 문자를 한 단어만 다르게 만들고 해당 단어도 사전에 존재하도록 생성됩니다. 대상 단어는 사전에 존재하며 모든 단어의 길이도 동일합니다. 프로그램은 시작에서 대상까지의 최단 경로 길이를 반환합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
Dictionary = {‘HEAL’, ‘HATE’, ‘HEAT’, ‘TEAT’, ‘THAT’, ‘WHAT’ , ‘HAIL’ ‘THAE’} Start = ‘HELL’ Target = ‘THAE’
출력
6
설명
HELL - HEAL - HEAT - TEAT - THAT - THAE
이 문제를 해결하기 위해 사전의 너비 우선 검색을 수행합니다. 이제 단계적으로 이전 문자에서 한 글자 떨어진 모든 요소를 찾습니다. 시작부터 대상까지 사다리를 만드세요.
솔루션 구현을 보여주는 프로그램,
예
#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; }
출력
Length of shortest chain from 'hell' to 'thae' is: 6