こんにちは
今回の学びは
・操作パスが多い時4方向によりO(4^n)のといはfor loopでdfsすることになるが着実に脱出できる時はしよう(枝刈り)
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
パッとみ組み合わせが多そうだなー
O(4^n)とか通らないだろー
という印象
少し考えましたが、O(N)とかいいアルゴは思いつかない。
ということで枝刈りというか、見つからなければそこで検索を辞めるので、そこまで大変なことにはならないだろう
と実装し始めます
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
O((4^n) / 10)くらいi don't know.
実際の実装はこちら
最終的には全部で43分かかりました。実装自体は通るものができるまでが役30分、最初のドラフトは15分で、考慮時間は18分でした。
これちらも
速度は満足いくものではありません。
直接実装に入ることができればちょうどくらいですか。
つまりはword search聞いて、パッと総当たりで枝刈りで実装に手を出せるかが勝負でしょうか。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])
arrows = (
(0, 1), # left
(0, -1), # right
(1, 0), # down
(-1, 0), # up
)
def valid_board(i, j):
if i < 0 or i >= m: return False
if j < 0 or j >= n: return False
return True
def get_board(i, j, default=""):
if valid_board(i, j): return board[i][j]
else: return default
def dfs(i, j, word, founded, path=[]) -> bool:
moji = get_board(i, j)
if word[founded] != moji: return False
founded += 1 # found 1 single char matched
path.append((i, j))
if founded == len(word): return True
ans = []
for arrow in arrows:
i_ = i+arrow[0]
j_ = j+arrow[1]
if not (i_, j_) in path: # already pased cordinate, don't go again
local = dfs(i_, j_, word, founded, path)
if local == True: return True # branch cut
# if branch cut above is not implemented, testcase 85/87 takes forever
# https://leetcode.com/submissions/detail/264052275/testcase/
ans.append(local)
if len(path) > 0: path.pop()
return any(ans)
for r in range(m):
for c in range(n):
if dfs(r, c, word, 0, path=[]):
return True
return False
。
特筆すべきは、当初、引っかかったようんにLTEにぶち当たります。
ここで私はテストケースを見て、これなら早く溶けるはずが、O(4^n)の樹海にはまってしまっています。
dfsで最初にTrueが見つかったら、さっと抜け出しましょう。これが今回の枝刈りですが、これの実装がうまくできていなかったの
if not (i_, j_) in path: # already pased cordinate, don't go again
local = dfs(i_, j_, word, founded, path)
if local == True: return True # branch cut
# if branch cut above is not implemented, testcase 85/87 takes forever
# https://leetcode.com/submissions/detail/264052275/testcase/
ans.append(local)
が原因でしたので、そこを以下のよう直しまして合格しました
・操作パスが多い時4方向によりO(4^n)のといはfor loopでdfsすることになるが着実に脱出できる時はしよう(枝刈り)
#1345pm start
(
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
],
"ABCCED", True
),
(
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
],
"SEE", True
),
(
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
],
"ABCB", False
),
# 1414pm failed at 36/87
# 1420pm fixed
(
[["a","a"]],
"aaa", False
)
# 1421pm failed at 85/87 by TLE
# current algo is O(4^n) worst
# 1428pm fixed
(
[["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","b"]],
"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
True
)
# 1428pm succeeded 524m 10.82%
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
他の人の解答を見てみましょう。
お、dfsが目立ちますね。https://leetcode.com/problems/word-search/discuss/385236/Python-Simple-DFS-(easy-to-understand)
こういうのが自前で書けて合格するようになってきたのは嬉しいです
dfsっぽいのですが黒板の消し方が秀逸です。まず検索済みはスペースで消してさらに終わったら元に戻すという以下の記述ね
board[i][j] = ' '
if self.snake(board, word, 1, [i, j]):
return True
else:
board[i][j] = word[0]
とってもいいですね。https://leetcode.com/problems/word-search/discuss/380452/faster-than-95.01-of-Python3
でもこれだけで95%行くんかな〜とも思います。ちなみに私のdfsは10％なのでw
実際には知らせると,272msで走りました。私のは524msでしたので
なるほど半分の時間で走ることができています。ただしそれでも200ms 台なので、みなさんdfsですね。
なので、黒板の使い方が秀逸なのではパフォにはそれほど影響してなくて多分stackの(list)操作で無駄しているかなー
とい印象です。時間があれば検証してみたいですが趣旨のアルゴリズム脳を鍛えるから
脱線するのでやめておきます。それにappend, pop()系はO(1)のはず、いやしかしlistの実装によってはlistの拡張でmallocが
ガッと増える時とかあるはず、こういう時にパフォーマンスが落ちる逆に言えばcpu使っているのかなー
という印象です （pythonのしくみでlistの実装取り上げた時に何かわかるはず！？乞うご期待！）
お次はword search IIですね ２があるんですね 🙂
まとめ
・操作パスが多い時4方向によりO(4^n)のといはfor loopでdfsすることになるが着実に脱出できる時はしよう(枝刈り)
以上です