두 단어(beginWord 및 endWord)가 있고 사전의 단어 목록이 있다고 가정하고 beginWord에서 endWord까지의 가장 짧은 변환 시퀀스의 길이를 찾으십시오. 다음과 같이 -
-
한 번에 하나의 문자만 변환할 수 있습니다.
-
변환된 각 단어에는 단어 목록이 있어야 합니다. beginWord는 변형된 단어가 아닙니다.
우리는 다음을 명심해야 합니다 -
-
이러한 변경 시퀀스가 없으면 0을 반환합니다.
-
모든 단어의 길이는 동일합니다.
-
모든 단어에는 소문자만 포함됩니다.
-
단어 목록에 중복이 없다고 가정할 수 있습니다.
따라서 입력이 다음과 같은 경우:beginWord ="hit", endWord ="cog" 및 wordlist =["hot", "dot", "dog", "lot", "log", "cog"]
그러면 가장 짧은 변환 하나가 히트 → 핫 → 점 → 개 → 톱니
이므로 출력은 5가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
putStar라는 메소드를 정의하면 j와 string s가 필요합니다. 이것은 다음과 같이 작동합니다 -
-
temp :=빈 문자열
-
범위 0에서 s – 1까지의 i에 대해
-
i =j이면 "*"를 연결하여 temp를 업데이트하고, 그렇지 않으면 s[i]를 temp와 연결하여 temp를 업데이트합니다.
-
-
기본 방법에서는 문자열 b, 문자열 e 및 단어 w 목록을 사용합니다. 이것은 −
와 같이 작동합니다. -
e가 w에 없거나 b가 비어 있거나 e가 비어 있거나 w가 비어 있으면 0을 반환합니다.
-
문자열 유형 키 및 배열 유형 값에 대한 맵 m을 정의합니다.
-
범위 0에서 w 크기까지의 i에 대해
-
x :=w[i]
-
j의 경우 :=0에서 x의 크기
-
인터 :=putStar(j, x)
-
m[inter]
에 x 삽입
-
-
-
대기열 q를 정의하고 쌍 (b, 1)을 q에 삽입
-
방문이라는 지도 만들기
-
q가 비어 있지 않은 동안
-
s :=q에서 전면 쌍, q에서 전면 요소 삭제
-
x :=쌍 s의 첫 번째 요소, l :=쌍 s의 두 번째 요소
-
범위 0에서 x 크기까지의 i에 대해
-
임시 :=putStar(i, x)
-
범위 0에서 m[temp]까지의 j에 대해
-
aa :=m[온도, j]
-
aa가 e와 같으면 l + 1을 반환합니다.
-
방문[aa]이 설정되지 않은 경우 쌍(aa, l + 1)을 삽입하고 방문[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