[アルゴリズムプール]単語の変換

問題の説明

2つの単語begin、target、単語の集合語があります.次のルールを使用して、beginからtargetに変換する最短変換プロセスを検索します.

一度に1文字しか変更できない.

単語にしか変換できません.

 たとえば、beginがhit、targetがcog、単語が[hot、dog、lot、log、cog]の場合、hit->hot->dot->dogなどの4つのステップで変換できます.
 2つの単語begin、target、および単語の集約語をパラメータとして指定する場合は、少なくともいくつかのステップを経てbeginをtargetに変換するには、解法関数を記述します.

せいげんじょうけん

各単語はアルファベット小文字のみで構成されている.

各単語の長さは3または10以下であり、すべての単語の長さは同じである.

単語は3個または50個以上あり、重複する単語はない.

beginとtargetは異なる.

変換できない場合は0を返します.

I/O例

I/O例説明

例1

問題の例は次のとおりです.

例2

単語にないため、ターゲットcogを変換できません.

に答える

from queue import Queue
import copy

def _word_compare(src_word, dest_word):
    diff_count = 0
    for i in range(len(src_word)):
        if src_word[i] != dest_word[i]:
            diff_count += 1
        
        if diff_count > 1:
            return False
    
    return True

def _search(begin, target, words):
    queue = Queue()
    depth = 0
    used = set()

    if target not in words:
        return 0

    queue.put((begin, 0))
    while(queue.qsize() > 0):
        cur_node = queue.get()
        src_word = cur_node[0]
        depth = cur_node[1]
        if _word_compare(src_word, target):
            return depth + 1


        for word in words:
            if _word_compare(src_word, word) and (word not in used):
                queue.put((word, depth + 1))
                used.add(word)
    return 0

def solution(begin, target, words):
    answer = _search(begin, target, words)
    return answer

  _word_compare(src_word, dest_word)2つの単語を入力し、1文字だけ差がある場合はTrueまたはFalseの関数を返します.内部使用_search  _search(begin, target, words)幅優先探索であり、現在のノードの単語_word_compareこのTrue人の単語を幅優先探索する関数である.targetがwordsに含まれていない場合は、0を返し、ナビゲートした単語をusedセットに追加し、ナビゲートされなくなります.(そうしないと、隣接する2つの単語に対してループが発生します.また、後から見つかった単語や隣接する単語であっても、前に測定した最短距離より短くはなりません)現在のノード上の単語をdepth+1とともにqueueに入れることで、再取り出し時にそのノードが深さを知ることができます.
 最初は最短経路に集中し,マルチ出口アルゴリズムにより解決を試みた.理論的には可能と考えられるが,実装上はコードが複雑になり,グラフが完成した後に経路を見つける必要があるため効率的ではないと考える.また,経路の長さが1であるため,マルチアウトアルゴリズムではなくBFSで問題を解決する方法が考えられる.

githubアドレス

https://github.com/bjih1999/algorithm/blob/master/programmers/DFS_BFS/%EB%8B%A8%EC%96%B4%20%EB%B3%80%ED%99%98/solution.py