326.ワード変換
18690 ワード
プログラマ
1. Python
from collections import deque
def solution(begin, target, words):
if target not in words:
return 0
queue = deque()
queue.append([begin, []])
while queue:
n, lst = queue.popleft()
for word in words:
if word not in lst:
diff = 0
for i in range(len(word)):
if word[i] != n[i]:
diff += 1
if diff == 1:
if word == target:
return len(lst) + 1
temp = lst[:]
temp.append(word)
queue.append([word, temp])
return 0
2. C++
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(string begin, string target, vector<string> words) {
int n = words.size();
int m = begin.size();
vector<int> visit(n, 0);
queue<pair<string, int>> q;
q.push({ begin, 0 });
int i, j, diff;
int answer = 0;
while (!q.empty()) {
string start = q.front().first;
int count = q.front().second;
q.pop();
for (i = 0; i < n; i++) {
diff = 0;
if (visit[i]) continue;
for (j = 0; j < m; j++) {
if (start[j] != words[i][j]) diff++;
}
if (diff == 1) {
if (words[i] == target) {
return count + 1;
}
visit[i] = 1;
q.push({words[i], count + 1 });
}
}
}
return answer;
}
3. JavaScript
function solution(begin, target, words) {
if(!words.includes(target)) return 0;
const n = words.length;
const m = begin.length;
let visit = Array.from({ length: n }, () => 0);
let answer = 0;
let q = [[begin, answer]];
while (q) {
let [start, count] = q.shift();
for (let i = 0; i < n; i++) {
let diff = 0;
if (visit[i]) continue;
for (let j = 0; j < m; j++) {
if (start[j] != words[i][j]) diff++;
}
if (diff == 1) {
if (words[i] == target) {
return count + 1;
}
visit[i] = 1;
q.push([words[i], count + 1]);
}
}
}
return answer;
}
Reference
この問題について(326.ワード変換), 我々は、より多くの情報をここで見つけました https://velog.io/@corone_hi/326.-단어-변환テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol