いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 127 word ladder

更新日:

こんにちは

 

今回の学びは

Image from https://leetcode.com/articles/word-ladder/

 

距離が1(つまりは隣のnode)をH*tのようなマスクで、前処理してグラフをつくっておく

・26^Nになるところを、必要ないdetailをうまく隠すことで、少なくしている。

・全てのポシビリティーを列挙するのではなく、今持っている手からの派生(ポシビリティー)から考えている

・ひところで言えば、最短距離を問われているのでグラフつくってBFSなんだけどグラフの作り方にH*tが秀逸

pythonのセットsetで|はunionのオペレーターだって

dequeはシングルスレッドでPOC的にはこれ。もちろん、dequeとして両端アクセスのみのときは、listsより、Queueより、dequeを使うぞー

・配列の何気ない走査 value in dictは配列サイズを意識して!O(N)はでかいと遅いから!

 

問題はword-ladder

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

中身は今回の記事では

こちらの記事がとてもわかりやすいので割愛します.

 

後日談、こちら実装まだしていなかったのと、別のサイトで同等の問題にであったので彩ちゃんレンジしました。

しかしながら、上記のマスク(h*t)みたいな、で、実装したけどLTEやったのです。

from collections import defaultdict
import sys
def rep(s, index, newstring):
    return s[:index] + newstring + s[index + 1:]

class Solution:
    def ladderLength(self, source: str, target: str, words: List[str]) -> int:
        
        lookup = defaultdict(list)
        links  = defaultdict(list)
        for word in words + [source]:
            for i in range(len(word)):
                link = rep(word, i, '-')
                lookup[link].append(word)
                links[word].append(link)
                #print(lookup)
        # print(lookup)
        # print(links)
        def rec(word, target, seen, dep):
            #print(word, target)
            if word == target:
                return dep
            else:
                seen.append(word)
                local = sys.maxsize
                for link in links[word]: # -it, b-t, -it
                    for next_word in lookup[link]: # list of words,
                        if next_word == word: continue
                        if not next_word in seen:
                            mini_dep = rec(next_word, target, seen, dep+1)
                            local = min(local, mini_dep)
                seen.remove(word)
                return local

        seen = []
        ans = rec(source, target, seen, 0)
        return -1 if ans == sys.maxsize else ans

しかし!これはleetcodeのword ladderではLTEになります!

しかも結構序盤で。19 / 40 test cases passed.

ということでメモ化をして高速化を図ります。

いつも苦戦するつ、recursiveのメモ化。うまく動いてくれません。これは私の弱みポイントが見つかりました。

BFSに切り替えて実装するも、これでもTLEとなった。若干記録は伸びた、がまだまだテストケースの中盤、29 / 40 test cases passed.

from typing import List
from collections import defaultdict
import sys

def rep(s, index, newstring):
    return s[:index] + newstring + s[index + 1:]

class Solution:
    def ladderLength(self, source: str, target: str, words: List[str]) -> int:

        lookup = defaultdict(list)
        links  = defaultdict(list)
        for word in words + [source]:
            for i in range(len(word)):
                link = rep(word, i, '-')
                lookup[link].append(word)
                links[word].append(link)
                #print(lookup)
        # print(lookup)
        # print(links)
        stack = [source]
        dep = 0
        while len(stack) > 0:
            dep += 1
            if dep > len(words): return 0
            local_stack = []
            while len(stack) > 0:
                word = stack.pop()
                #print("checking %s to %s" % (word, target))
                if word == target:
                    return dep
                for link in links[word]:
                    for next_word in lookup[link]:
                        if next_word != word:
                            if next_word not in local_stack:
                                local_stack.append(next_word)
                #print("local_stack:%s" % local_stack)
            stack = local_stack
        return 0

で、根本的にダメそうなので

discussionをみました。https://leetcode.com/problems/word-ladder/discuss/473774/python-two-end-solution-100ms

アルファベットで26ループして、wordsを走査する方法を検証して

みます。

ということで、

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        counts = 1
        letters = 'abcdefghijklmnopqrstuvwxyz'
        if beginWord in wordList:
            wordList.remove(beginWord)
        word_dic = {i:1 for i in wordList} # for O(1) search
        l = set([beginWord])
        r = set([endWord])
        ll = set([beginWord]) # record all the words appeared
        #rr = set([endWord])

        while l:
            tmp = []
            for word in l:
                for ch in letters:
                    for i in range(len(word)):
                        new = word[:i]+ch+word[i+1:]
                        if (new not in ll) & (new in word_dic):
                            tmp.append(new)
            l = set(tmp)
            counts += 1
            ll = ll | l

            if l & r:
                return counts
            # これを入れたら動かんかったし、読んでいてもおかしいコード。だから外す。
            # if len(l) > len(r):
            #     l, r, ll, rr = r, l, rr, ll # for less branches


        return 0

pythonのセットsetで|はunionのオペレーターだって。(geekforgeeks)

Input :
A = {0, 2, 4, 6, 8}
B = {1, 2, 3, 4, 5}

Output :
 Union : [0, 1, 2, 3, 4, 5, 6, 8]
 Intersection : [2, 4]
 Difference : [8, 0, 6]
 Symmetric difference : [0, 1, 3, 5, 6, 8]

In Python, below quick operands can be used for different operations.

| for union.
& for intersection.
– for difference
^ for symmetric difference

 

しかしここで終わっていは行けない!もっと別の解法もみてみましょう。

https://leetcode.com/problems/word-ladder/discuss/475304/Python-bi-directional-approach-which-takes-only-100ms

は両端から攻める技です。word ladder iiのdiscussionの解法を参考にしたもののようです

ここでは

from collections import deque

を扱っているので、まずはこれの勉強だ。pythonのQueue()はつあったことあったが、dequeはない。

まずはdequeとは? メリっとは両端へのアクセスでデメリは両端以外へのアクセス。リストとの違いをおさえよ。

Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと、データをキューやスタック、デック(両端キュー)として効率的に扱うことができる。collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント

標準のリストをキューやスタック、デック(両端キュー)として使うことも可能だが、リストでは先頭の要素に対する削除や追加(挿入)は処理速度が遅いためdequeのほうが効率的。なお、dequeには、両端以外の要素へのアクセスが遅いというデメリットもあるので注意。

出典: https://note.nkmk.me/python-collections-deque/

かんたんに使ってみとQueue()より扱いやすい。俺はこっちの好きだ。

しかもdequeは queue(FIFO)としても、stack(FILO)としても、deque(double-ended両端queue)としても使えるし

公式ではスレッドセーフって書いてあるし、queue.Queueより良いじゃん!と思いましたが違いは、queue.Queueは真にスレッドセーフを謳っていて、dequeはappend, popはスレッドセーフとしかドキュメントには書かれていないのです。

stackoverflow, is-this-deque-thread-safe-in-pythonでも似たような、質問がありましたし、このブログ記事でもQueueはスレッドセーフとありましたので、

私もdequeはシングルスレッドでPOC的にはこれ。もちろん、dequeとして両端アクセスのみのときは、listsより、Queueより、dequeを使うぞー、さらにスレッドセーフにlock実装とかすれば本番でも十分dequeつかえるんじゃない。普通にLIFOをマルチスレッドで扱いたいときは、Queueね。と、そういう理解をしました。

In [1]: from collections import deque
In [2]: d = deque()
In [3]: d
Out[3]: deque([])

In [4]: d.append(3)
In [5]: d.append('miso')

In [6]: d
Out[6]: deque([3, 'miso'])

In [7]: d.pop()
Out[7]: 'miso'

In [9]: d.append('miso')
In [10]: d.append('soup')


In [11]: d
Out[11]: deque([3, 'miso', 'soup'])

In [12]: d.popleft()
Out[12]: 3

In [13]: d
Out[13]: deque(['miso', 'soup'])


In [15]: d.appendleft(4)
In [16]: d
Out[16]: deque([4, 'miso', 'soup'])

In [17]: d.rotate()
In [18]: d
Out[18]: deque(['soup', 4, 'miso'])

In [19]: d.pop()
Out[19]: 'miso'
In [20]: d.pop()
Out[20]: 4
In [21]: d.pop()
Out[21]: 'soup'
In [22]: d.pop()
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-22-663961784a31> in <module>
----> 1 d.pop()

IndexError: pop from an empty deque

でqueueの勉強もしたところで、

ノートで処理の様子を確認します。一回目のループを緑2回目のループを赤で、3回目のループを青であらわしています。

さらにイメージしやすいように、ノードの繋がり方の絵は下のようになっています。

 

https://leetcode.com/problems/word-ladder/discuss/475304/Python-bi-directional-approach-which-takes-only-100ms

実際走らせてみると!直前の実装では584msが一気に108msへ約600%のスピード改善です。

こんな人を雇いたいですよね。

 

 

ここで最初のsolutionのアイデアに立ち返る。何故LTEだったのか?アイデアはasciiコードを舐めるより良いはずだ

ということで調べたところ、以下の処理でべらぼうに時間がかかっておりました。これがめちゃめちゃ遅いとコメントした

if next_word not in local_stack:です。これを改善しようと思います。

class Solution:
    @timeit
    def ladderLength(self, source: str, target: str, words: List[str]) -> int:
        lookup = defaultdict(list)
        links  = defaultdict(list)
        for word in words + [source]:
            for i in range(len(word)):
                link = rep(word, i, '-')
                lookup[link].append(word)
                links[word].append(link)

        if target not in words: return 0
        stack = [source]
        mini = sys.maxsize
        dep = 0
        while len(stack) > 0:
            dep += 1
            if dep > len(words): return 0
            local_stack = []
            while len(stack) > 0:
                word = stack.pop()
                #print("checking %s to %s" % (word, target))
                if word == target:
                    mini = min(mini, dep)
                    return mini
                for link in links[word]: # O(1)
                    for next_word in lookup[link]: # O(1)
                        if next_word != word:  # # O(len(word))
                            if next_word not in local_stack: # O(n)これがめちゃめちゃ遅い
                                local_stack.append(next_word)
                            #pass
                #print("local_stack:%s" % local_stack)
            stack = local_stack
        return 0 if mini == sys.maxsize else ans + 1

改善したバージョンはこちらです。改善方法は、setで扱うか、別のルックアップテーブルをhashで持つかなどが考えられましたが

今回はsetで実装してみました。

見事いけました。まだ316msと遅いけど、もともとのアイデアでも行けることは証明できました。setでaddもまだ改善ポイントかなとは思います。dequeのが速いかと。

それでも満足です。

from collections import defaultdict
import time
def rep(s, index, newstring):
    return s[:index] + newstring + s[index + 1:]

class Solution:
    def ladderLength(self, source: str, target: str, words: List[str]) -> int:
        lookup = defaultdict(list)
        links  = defaultdict(list)
        for word in words + [source]:
            for i in range(len(word)):
                link = rep(word, i, '-')
                lookup[link].append(word)
                links[word].append(link)

        if target not in words: return 0
        stack = [source]
        mini = sys.maxsize
        dep = 0
        while len(stack) > 0:
            dep += 1
            if dep > len(words)+1: return 0
            local_stack = set()
            while len(stack) > 0:
                word = stack.pop()
                #print("checking %s to %s" % (word, target))
                if word == target:
                    mini = min(mini, dep)
                    return mini
                for link in links[word]: # O(1)
                    for next_word in lookup[link]: # O(1)
                        if next_word != word:  # # O(len(word))
                            #if next_word not in local_stack: # O(n)これ遅いかも。
                            local_stack.add(next_word)
                #print("local_stack:%s" % local_stack)
            stack = list(local_stack)
        return 0 if mini == sys.maxsize else ans + 1

 

*追記*

後日、再チャレンジ。またも解けなかった。dfsで再帰で挑んで、見事砕けている。。。

bfsとキューで実装しよう。bfsはキューで。

惜しいところまではいったのが、でもツワモノはちゃんとrecursiveでも実装できています。このように

https://leetcode.com/problems/word-ladder/discuss/418916/Python-BFS-recursion-solution-not-storing-global-min_length

でも、私はqueueで実装したほうが無難だし。bfsなので、bfsとキューで実装しよう。bfsはキューで。

実装例:https://leetcode.com/problems/word-ladder/discuss/494234/BFS-simple-BFS-and-2-end-BFS-in-Python

class Solution:
    def ladderLength(self, S: str, T: str, words: List[str]) -> int:
        if S is None or T is None: return 0
        if len(S) != len(T): return 0
        if T not in words: return 0       # tO(N)

        # hit -> hot
        # hit -> a(it), b(it), c(it), ... z(it)
        # 3 * 26 --------> len(M) * 26

        """
        hit
        visited = 
        """
        lookup = { word:0 for word in words}
        lookup[S] = 0
        #print(lookup)
        import string
        from functools import lru_cache
        cache = {}
        def dfs(curr):
            #print(sS"dfs(%s)" % (curr))
            if curr not in lookup or lookup[curr] == 1: return []
            lookup[curr] = 1
            local = None
            for i in range(len(curr)):
                #print(curr[:i] + '*' + curr[i+1:])
                for r in string.ascii_lowercase:
                    tugi = curr[:i] + r + curr[i+1:]
                    if tugi == curr: continue
                    #print(tugi, end=',')
                    if tugi in lookup:
                        #print(tugi)
                        if tugi == T:
                            return [tugi]
                        ret = dfs(tugi)
                        if isinstance(ret, list) and len(ret) > 0:
                            tmp = [tugi] + ret
                            if local is None:
                                local = tmp
                            else:
                                if len(tmp) < len(local):
                                    local = tmp
            return [] if local is None else local

        ans = dfs(S)
        if len(ans) > 0:
            ans = [S] + ans
        #print(ans)
        return len(ans)

 

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

・距離が1(つまりは隣のnode)をH*tのようなマスクで、前処理してグラフをつくっておく

・配列の何気ない走査 value in dictは配列サイズを意識して!O(N)はでかいと遅いから!

・bfsとキューで実装しよう。bfsはキューで。

 

 

まとめ

距離が1(つまりは隣のnode)をH*tのようなマスクで、前処理してグラフをつくっておく

・26^Nになるところを、必要ないdetailをうまく隠すことで、少なくしている。

・全てのポシビリティーを列挙するのではなく、今持っている手からの派生(ポシビリティー)から考えている

・ひところで言えば、最短距離を問われているのでグラフつくってBFSなんだけどグラフの作り方にH*tが秀逸

pythonのセットsetで|はunionのオペレーターだって

dequeはシングルスレッドでPOC的にはこれ。もちろん、dequeとして両端アクセスのみのときは、listsより、Queueより、dequeを使うぞー

・配列の何気ない走査 value in dictは配列サイズを意識して!O(N)はでかいと遅いから!

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.