Backtracking / DFS / BFS

Word Search

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if board is None or len(board) == 0:
            return False
        visited = [[False for _ in row] for row in board]
        for i, row in enumerate(board):
            for j in range(len(row)):
                result = self.dfs(board, visited, i, j, word, 0)
                if result:
                    return True
        return False
        
    def dfs(self, board, visited, i, j, word, pos):
        if pos == len(word):
            return True
        if i < 0 or i >= len(board) or \
           j < 0 or j >= len(board[0]):
            return False
        if board[i][j] != word[pos]:
            return False
        if visited[i][j]:
            return False
        
        visited[i][j] = True 
        result = self.dfs(board, visited, i-1, j, word, pos+1) or \
                 self.dfs(board, visited, i+1, j, word, pos+1) or \
                 self.dfs(board, visited, i, j-1, word, pos+1) or \
                 self.dfs(board, visited, i, j+1, word, pos+1)
        visited[i][j] = False
        return result

N-Queens

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        result = []
        self.dfs(n, 0, [-1]*n, result)
        for i in range(len(result)):
            for j in range(n):
                pos = result[i][j]
                result[i][j] = ''.join(['Q' if k==pos else '.' for k in range(n)])
        return result
        
    def dfs(self, n, pos, path, result):
        if not self.isValid(path, pos-1):
            return
        if pos == n:
            result.append(list(path))
            return
        for i in range(n):
            path[pos] = i
            self.dfs(n, pos+1, path, result)
            path[pos] = -1
        
    def isValid(self, path, pos):
        for i in range(pos):
            if path[i] == path[pos]:
                return False
            if abs(pos-i) == abs(path[i]-path[pos]):
                return False
        return True

Sudoku Solver

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n <= 0:
            return []
        return self.dfs(1, n)
        
    def dfs(self, start, end):
        if start > end:
            return [None]
        result = []
        for i in range(start, end+1):
            left_lists = self.dfs(start, i-1)
            right_lists = self.dfs(i+1, end)
            for left in left_lists:
                for right in right_lists:
                    node = TreeNode(i)
                    node.left, node.right = left, right
                    result.append(node)
        return result

Word Ladder II

from collections import deque

class ListNode(object):
    def __init__(self, val, count):
        self.val = val
        self.count = count
        self.prev = None

class Solution(object):
    def findLadders(self, beginWord, endWord, wordlist):
        """
        :type beginWord: str
        :type endWord: str
        :type wordlist: Set[str]
        :rtype: List[List[int]]
        """
        return self.bfs(beginWord, endWord, wordlist)
        
    def bfs(self, start, end, dict):
        if end not in dict:
            dict.add(end)
        queue = deque()
        queue.append((start, 1))
        paths = {start:(1, [])}  
        while queue:
            s, count = queue.popleft()
            if s == end:
                break
            for i in range(len(s)):
                for j in range(26):
                    c = chr(ord('a') + j)
                    temp = s[:i]+c+s[i+1:]
                    if temp in dict:
                        if temp not in paths:
                            paths[temp] = (count+1, [s])
                            queue.append((temp, count+1))
                        elif count+1 == paths[temp][0]:
                            paths[temp][1].append(s)
        return self.buildPath(paths, start, end)
        
    def buildPath(self, paths, start, end):
        if start == end:
            return [[start]]
        result = []
        if end in paths:
            for prev in paths[end][1]:
                prev_result = self.buildPath(paths, start, prev)
                for prev_list in prev_result:
                    result.append(prev_list + [end])
        return result
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,743评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,296评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,285评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,485评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,581评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,821评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,960评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,719评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,186评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,516评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,650评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,329评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,936评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,757评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,991评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,370评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,527评论 2 349

推荐阅读更多精彩内容

  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,738评论 2 36
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,738评论 0 33
  • angular-ui-select 的TAGGING功能 angular-ui-select 是angular-u...
    zxqian阅读 531评论 0 1
  • 背景 恩,最近实用emacs写一些东西的时候觉得效率不是很高,就想着,有没有更好的IDE或者编辑器能够替代下。虽然...
    文卿阅读 11,655评论 13 2
  • 这是2013年4月14日在公园里拍的组照中的一张,我取名叫“小菊”。左上方有我的特殊标记GOLY PHOYO。其实...
    有趣的谷粒阅读 401评论 1 0