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