326.ワード変換


プログラマ

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