Graph

In a graph, the edges point out to some neighbors and point back from some other neighbors. In a network with feedbacks, local decision depends on all the neighbors. We need to start from a node then visits all the adjacent nodes. 

Q: Return a deep copy (clone) of the graph.

S1:

"""

# Definition for a Node.

class Node:

def __init__(self, val = 0, neighbors = None):

self.val = val

self.neighbors = neighbors if neighbors is not None else []

"""

class Solution:

def cloneGraph(self, node: 'Node') -> 'Node':

oldToCopy = {}

def dfs(node: 'Node') -> 'Node':

if node in oldToCopy:

return oldToCopy[node]

copy = Node(node.val)

oldToCopy[node] = copy

for nei in node.neighbors:

copy.neighbors.append(dfs(nei))

return copy

if not node:

return None

dfs(node)

return oldToCopy[node]

#O(V+E), O(V)

Graph is about node relationships, it is not about picture. A matrix cell has 4 edges connecting to the 4 adjacent cells in a graph. 

Q: Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Explanation: Notice that an 'O' should not be flipped if:

- It is on the border, or

- It is adjacent to an 'O' that should not be flipped.

The bottom 'O' is on the border, so it is not flipped.

The other three 'O' form a surrounded region, so they are flipped.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

S1: Pay attention to how we navigate the 4 adjacent cells and detect boundary.

class Solution:

def solve(self, board: List[List[str]]) -> None:

"""

Do not return anything, modify board in-place instead.

"""

m = len(board)

n = len(board[0])

dirs = [(1,0),(0,1),(-1,0),(0,-1)]

def dfs(r: int, c: int):

if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != 'O':

return

board[r][c] = 'T'

for d in dirs:

dfs(r + d[0], c + d[1])

for r in range(m):

for c in range(n):

if r in [0, m-1] or c in [0, n-1] and board[r][c] == 'O':

dfs(r, c)

for r in range(m):

for c in range(n):

if board[r][c] == 'O':

board[r][c] = 'X'

elif board[r][c] == 'T':

board[r][c] = 'O'

#O(mn), O(mn)

Q: A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]

Output: 1

Example 2:

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Output: 2

S1:

class Solution:

def minMutation(self, start: str, end: str, bank: List[str]) -> int:

queue = deque([(start, 0)])

seen = {start}

while queue:

node, steps = queue.popleft()

if node == end:

return steps

for c in "ACGT":

for i in range(len(node)):

neighbor = node[:i] + c + node[i + 1:]

if neighbor not in seen and neighbor in bank:

queue.append((neighbor, steps + 1))

seen.add(neighbor)

return -1

#O(n), O(n)

Q: Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.

void addWord(word) Adds word to the data structure, it can be matched later.

bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word contains lower case letters, it may contain dots '.' where dots can be matched with any letter.

Example:

Input

["WordDictionary","addWord","addWord","addWord","search","search","search","search"]

[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

Output

[null,null,null,null,false,true,true,true]

Explanation

WordDictionary wordDictionary = new WordDictionary();

wordDictionary.addWord("bad");

wordDictionary.addWord("dad");

wordDictionary.addWord("mad");

wordDictionary.search("pad"); // return False

wordDictionary.search("bad"); // return True

wordDictionary.search(".ad"); // return True

wordDictionary.search("b.."); // return True

S1: when key is string, we can use trie to store the words. For wildcard search, we use dfs.

class TrieNode:

def __init__(self, isWord = False):

self.isWord = isWord

self.children = {}

class WordDictionary:

def __init__(self):

self.root = TrieNode()

def addWord(self, word: str) -> None:

cur = self.root

for c in word:

if c not in cur.children:

cur.children[c] = TrieNode()

cur = cur.children[c]

cur.isWord = True

#O(w)

def search(self, word: str) -> bool:

def dfs(root: TrieNode, start: int) -> bool:

cur = root

for i in range(start, len(word)):

c = word[i]

if c != '.':

if c not in cur.children:

return False

else:

cur = cur.children[c]

else:

for child in cur.children.values():

if dfs(child, i+1):

return True

return False

return cur.isWord

#O(wn)

return dfs(self.root, 0)

# Your WordDictionary object will be instantiated and called as such:

# obj = WordDictionary()

# obj.addWord(word)

# param_2 = obj.search(word)

The spirit of dfs is backtrack, we usually use backtrack to enumerate all the possibilities in a state space.

Q: The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4

Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle.

Example 2:

Input: n = 1

Output: 1

S1: pay attention to diagonal and anti-diagonal cells and the removal from visited sets.

class Solution:

def totalNQueens(self, n: int) -> int:

cols = set()

diag = set()

ndiag = set()

res = 0

def backtrack(r: int) -> None:

nonlocal res

if r == n:

res+=1

return

for i in range(n):

if i in cols or (r+i) in diag or (r-i) in ndiag:

continue

cols.add(i)

diag.add(r+i)

ndiag.add(r-i)

backtrack(r+1)

cols.remove(i)

diag.remove(r+i)

ndiag.remove(r-i)

backtrack(0)

return res

#O(nn), O(n)

Q:

S1: