こんにちは
今回の学びは
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
しかしここで終わっていは行けない！もっと別の解法もみてみましょう。
は両端から攻める技です。word ladder iiのdiscussionの解法を参考にしたもののようです
ここでは
from collections import deque
を扱っているので、まずはこれの勉強だ。pythonのQueue()はつあったことあったが、dequeはない。
まずはdequeとは？ メリっとは両端へのアクセスでデメリは両端以外へのアクセス。リストとの違いをおさえよ。
Pythonの標準ライブラリcollectionsモジュールの
deque型を使うと、データをキューやスタック、デック（両端キュー）として効率的に扱うことができる。collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント標準のリストをキューやスタック、デック（両端キュー）として使うことも可能だが、リストでは先頭の要素に対する削除や追加（挿入）は処理速度が遅いため
dequeのほうが効率的。なお、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の勉強もしたところで、
ノートで処理の様子を確認します。一回目のループを緑で２回目のループを赤で、３回目のループを青であらわしています。
さらにイメージしやすいように、ノードの繋がり方の絵は下のようになっています。
実際走らせてみると！直前の実装では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でも実装できています。このように。
でも、私は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)はでかいと遅いから！
以上です