DFS

Last updated 3 years ago

Was this helpful?

DFS

Start room 0 to DFS all rooms. Use a set to keep track of the visited rooms. Return true if the visited number of rooms equals total number of rooms.

public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    Set<Integer> visited = new HashSet<>();
    dfs(0, rooms, visited);
    return visited.size() == rooms.size();
}

private void dfs(int curt, List<List<Integer>> rooms, Set<Integer> visited) {
    visited.add(curt);
    if (rooms.get(curt) == null) return;
    for (int next : rooms.get(curt)) {
        if (visited.contains(next)) continue;
        dfs(next, rooms, visited);
    }
}

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    dfs(image, sr, sc, image[sr][sc], newColor);
    return image;
}

private void dfs(int[][] image, int x, int y, int orginal, int newColor) {
    if (x < 0 || x >= image.length || y < 0 || y >= image[0].length 
    || image[x][y] != orginal 
    || image[x][y] == newColor ) return;
    image[x][y] = newColor;
    dfs(image, x + 1, y, orginal, newColor);
    dfs(image, x - 1, y, orginal, newColor);
    dfs(image, x, y + 1, orginal, newColor);
    dfs(image, x, y - 1, orginal, newColor);
}

Use a HashMap to store correlation. While traversing, if map contains this node, return the corresponding clone. Create clone, add the corresponding new clone to the neighbors list.

T: O(n)

Map<Node, Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
    return dfs(node);
}

private Node dfs(Node curt) {
    if (curt == null) return null;
    if (map.containsKey(curt)) return map.get(curt);
    Node clone = new Node(curt.val, new ArrayList<>());
    map.put(curt, clone);
    for (Node next : curt.neighbors) {
        map.get(curt).neighbors.add(dfs(next));
    }
    return clone;
}

DFS to fill the edge nodes and its linked nodes to a temporary state (eg. 'T'). Fill the middle nodes then fill all 'T's back to it is original state 'O'.

int[][] dirs = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public void solve(char[][] board) {
    if (board == null || board.length == 0 || board[0].length == 0) return;
    int m = board.length, n = board[0].length;
    // fill boarder 'O' as 'T';
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') fill(board, i, 0);
        if (board[i][n - 1] == 'O') fill(board, i, n - 1);
    }
    for (int j = 0; j < n ; j++) {
        if (board[0][j] == 'O') fill(board, 0, j);
        if (board[m - 1][j] == 'O') fill(board, m - 1, j);
    }
    // flip all 'O' to 'X'
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
        }
    }
    
    // flip all 'T' to 'O'
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'T') board[i][j] = 'O';
        }
    }
}

private void fill(char[][] board, int x, int y) {
    if (!inbound(board, x, y) || board[x][y] != 'O') return;
    board[x][y] = 'T';
    for (int[] d : dirs) {
        fill(board, x + d[0], y + d[1]);
    }
}

private boolean inbound(char[][] board, int x, int y) {
    return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}

directions = [[0,1],[1,0],[-1,0], [0,-1]]
def solve(self, board: List[List[str]]) -> None:
    if not board or len(board) == 0 or len(board[0]) == 0:
        return
    m = len(board)
    n = len(board[0])
    queue = []
    for i in range(0, m):
        if board[i][0] == "O":
            queue.append([i, 0])
        if board[i][n - 1] == "O":
            queue.append([i, n - 1])
    for j in range(0, n):
        if board[0][j] == "O":
            queue.append([0, j])
        if board[m - 1][j] == "O":
            queue.append([m - 1, j])
    while queue:
        x, y = queue.pop(0)
        board[x][y] = "B"  
        for d in self.directions:  ## x= 3,y=1
            nx = x + d[0]
            ny = y + d[1]
            if self.inbound(board, nx, ny) and board[nx][ny] == "O":
                queue.append([nx, ny])
    
    for i in range(0, m):
        for j in range(0, n):
            if board[i][j] == "O":
                board[i][j] = "X"
            if board[i][j] == "B":
                board[i][j] = "O"
    

def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int numEnclaves(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) {
            fill(grid, i, 0, 2);
        }
        if (grid[i][n - 1] == 1) {
            fill(grid, i, n - 1, 2);
        }
    }
    for (int i = 0; i < n; i++) {
        if (grid[0][i] == 1) {
            fill(grid, 0, i, 2);
        }
        if (grid[m - 1][i] == 1) {
            fill(grid, m - 1, i, 2);
        }
    }
    int total = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                total += fill(grid, i, j, 0);
            }
        }
    }
    return total;
}

private int fill(int[][] grid, int x, int y, int fillNum) {
    if (!inbound(grid, x, y) || grid[x][y] != 1) {
        return 0;
    }
    int total = 1;
    grid[x][y] = fillNum;
    for (int[] d : dir) {
        int nx = x + d[0], ny = y + d[1];
        total += fill(grid, nx, ny, fillNum);
    }
    return total;
}

private boolean inbound(int[][] grid, int x, int y) {
    return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}

When reach a node of an Island, DFS all nodes and fill the grid with '0'. This would eliminate repeated traversal.

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    this.n = grid.length;
    this.m = grid[0].length;
    this.grid = grid;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 
        || i >= grid.length 
        || j < 0 
        || j >= grid[0].length 
        || grid[i][j] != '1') return;
    grid[i][j] = '0';
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
}

directions = [[0,1],[1,0],[-1,0], [0,-1]]
def numIslands(self, grid: List[List[str]]) -> int:
    count = 0
    for x in range(0, len(grid)):
        for y in range(0, len(grid[0])):
            if grid[x][y] == "1":
                self.bfs(grid, x, y)
                count += 1
    return count

def bfs(self, grid, x, y):
    queue = []
    queue.append([x, y])
    grid[x][y] = "0"
    while queue:
        curt = queue.pop(0)   
        for d in self.directions:
            nextx = curt[0] + d[0]  
            nexty = curt[1] + d[1]
            if nextx >= 0 and nextx < len(grid) and nexty >= 0 and nexty < len(grid[0]) and grid[nextx][nexty] == "1":
                queue.append([nextx, nexty])
                grid[nextx][nexty] = "0"

directions = [[0,1],[1,0],[-1,0], [0,-1]]
def numIslands(self, grid: List[List[str]]) -> int:
    count = 0
    for x in range(0, len(grid)):
        for y in range(0, len(grid[0])):
            if grid[x][y] == "1":
                self.dfs(grid, x, y)
                count += 1
    return count

def dfs(self, grid, x, y):
    grid[x][y] = "0"
    for d in self.directions:
        nextx = x + d[0]  
        nexty = y + d[1]
        if nextx >= 0 and nextx < len(grid) and nexty >= 0 and nexty < len(grid[0]) and grid[nextx][nexty] == "1":
            self.dfs(grid, nextx, nexty)

public int maxAreaOfIsland(int[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int max = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                max = Math.max(max, dfs(grid, i, j));
            }
        }
    }
    return max;
}

private int dfs(int[][] grid, int x, int y) {
    if (!inbound(grid, x, y) || grid[x][y] == 0) return 0;
    int count = grid[x][y] == 1 ? 1 : 0;
    grid[x][y] = 0;
    count += dfs(grid, x + 1, y) 
           + dfs(grid, x - 1, y) 
           + dfs(grid, x, y + 1) 
           + dfs(grid, x, y - 1);
    return count;
}

private boolean inbound(int[][] board, int x, int y) {
    return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}

directions = [[0,1],[1,0],[-1,0],[0,-1]]
res = 0
curtRes = 0
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                self.curtRes = 0
                self.dfs(grid, i, j)
                self.res = max(self.res, self.curtRes)
    return self.res

def dfs(self, grid, x, y):
    grid[x][y] = 0
    self.curtRes += 1
    for dx, dy in self.directions:
        nx = x + dx
        ny = y + dy
        if self.inbound(grid, nx, ny) and grid[nx][ny] == 1:
            self.dfs(grid, nx, ny)
    
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

directions = [[0,1],[1,0],[-1,0],[0,-1]]
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    res = 0
    m = len(grid)
    n = len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                res = max(res, self.dfs(grid, i, j))
    return res

def dfs(self, grid, x, y):
    if not self.inbound(grid, x, y) or grid[x][y] != 1:
        return 0
    count = 0
    if grid[x][y] == 1:
        count = 1
    grid[x][y] = 0
    for dx, dy in self.directions:
        nx = x + dx
        ny = y + dy
        count += self.dfs(grid, nx, ny)
    return count
    
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

Distinctness can be determined by the shape of the island, however saving the shape might be a bit difficult. An easier way is to save the pattern of traversal.

Starting with top left corner fo the island, DFS and use a StringBuilder to save the directions. Save "0" at when breaking out the recursion

sb.append("0");

since it represents the pattern of recursive traversal, move both forward and backwards.

int[][] dirs = {{1,0},{0,1},{-1,0}, {0,-1}};
boolean[][] visited;
public int numDistinctIslands(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    visited = new boolean[m][n];
    Set<String> set = new HashSet<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                StringBuilder sb = new StringBuilder();
                dfs(grid, i, j, 0, sb);
                set.add(sb.toString());
            }
        }
    }
    return set.size();
}

private void dfs(int[][] grid, int x, int y, int dir, StringBuilder sb) {
    visited[x][y] = true;
    grid[x][y] = 0;
    sb.append(dir);
    for (int i = 0; i < dirs.length; i++) {
        int next_x = x + dirs[i][0];
        int next_y = y + dirs[i][1];
        if (next_x >= 0 
            && next_y >= 0 
            && next_x < grid.length 
            && next_y < grid[0].length 
            && grid[next_x][next_y] == 1 
            && !visited[next_x][next_y]) {
            dfs(grid, next_x, next_y, i, sb);
        }
    }
    sb.append("0");
}

directions = [[-1,0],[0,1], [1,0],[0,-1]]
path = ""
def numDistinctIslands(self, grid: List[List[int]]) -> int:
    res = set()
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                self.path = ""
                self.dfs(grid, i, j)
                print(self.path)
                res.add(self.path)
    return len(res)

def dfs(self, grid, x, y):
    if not self.inbound(grid, x, y) or grid[x][y] != 1:
        return
    grid[x][y] = 0
    for k in range(0, 4):
        self.path += str(k) + ","
        nx = x + self.directions[k][0]
        ny = y + self.directions[k][1]
        self.dfs(grid, nx, ny)
    
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

This problem is similar as other 'island on graph' problems. However, the DFS is quite tricky. You have to make sure all nodes are filled. Also the DFS of each level can't terminate early. For example:

res = dfs(grid, next_x, next_y) && res;

is the only way to complete the traversal. Other ways such as:

if (true) : return true
if (false): return false
res = res && dfs(grid, next_x, next_y)

will terminate the recursion early.

public int closedIsland(int[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 0 && dfs(grid, i, j)) {
                count++;
            }
        }
    }
    return count;
}
int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
private boolean dfs(int[][] grid, int x, int y) {
    if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
        return false;
    }
    if (grid[x][y] == 1 || grid[x][y] == 2) {
        return true;
    }
    boolean res = true;
    grid[x][y] = 2;
    for (int[] dir : dirs) {
        int next_x = x + dir[0];
        int next_y = y + dir[1];
        res = dfs(grid, next_x, next_y) && res;
    }
    return res;
}

305. Number of Islands II305. Number of Islands II

DFS when see the ship

public int countBattleships(char[][] board) {
    int count = 0;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 'X') {
                count++;
                dfs(board, i, j, true);
                board[i][j] = 'X';
                dfs(board, i, j, false);
            }
        }
    }
    return count;
}

private void dfs(char[][] board, int x, int y, boolean hori) {
    if (!inbound(board, x, y) || board[x][y] != 'X') return;
    board[x][y] = '.';
    if (hori) {
        dfs(board, x, y + 1, hori);
        dfs(board, x, y - 1, hori);
    } else {
        dfs(board, x + 1, y, hori);
        dfs(board, x - 1, y, hori);
    }
}

private boolean inbound(char[][] board, int x, int y) {
    return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}

Solution2: one pass

public int countBattleships(char[][] board) {
    int m = board.length;
    if (m==0) return 0;
    int n = board[0].length;
    
    int count=0;
    
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (board[i][j] == '.') continue;
            if (i > 0 && board[i-1][j] == 'X') continue;
            if (j > 0 && board[i][j-1] == 'X') continue;
            count++;
        }
    }
    return count;
}

Get number of mines of each grid. If mine count == 0, set board to 'B' and keep traversing. Otherwise set the grid to that mine number.

T: O( 8* (m*n) ^ 2)

    int[][] dirs = new int[][]{
        {0,1}, {0, -1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1},{-1,-1}};
    public char[][] updateBoard(char[][] board, int[] click) {
        int x = click[0];
        int y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }
        dfs(board, x, y);
        return board;
    }
    
    private void dfs(char[][] board, int x, int y) {
        if (!inbound(board, x, y) || board[x][y] != 'E') return;
        int num = getMineNum(board, x, y);
        if (num == 0) {
            board[x][y] = 'B';
            for (int[] dir : dirs) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                dfs(board, newX, newY);
            }
        } else {
            board[x][y] = (char) ('0' + num);
        }
    }
    
    private int getMineNum(char[][] board, int x, int y) {
        int count = 0;
        for (int[] dir : dirs) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (inbound(board, newX, newY) && 
                (board[newX][newY] == 'M' || board[newX][newY] == 'X')) {
                count++;
            }
        }
        return count;
    }
    
    private boolean inbound(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

public int depthSum(List<NestedInteger> nestedList) {
    return dfs(nestedList, 1);
}

private int dfs(List<NestedInteger> nestedList, int level) {
    int sum = 0;
    for (NestedInteger ni : nestedList) {
        if (ni.isInteger()) {
            sum += ni.getInteger() * level;
        } else {
            sum += dfs(ni.getList(), level + 1);
        }
    }
    return sum;
}

public int depthSumInverse(List<NestedInteger> nestedList) {
    int maxDepth = getDepth(nestedList);
    return getSum(nestedList, maxDepth);
}

private int getSum(List<NestedInteger> nestedList, int depth) {
    int sum = 0;
    for (NestedInteger ni : nestedList) {
        if (ni.isInteger()) {
            sum += depth * ni.getInteger();
        } else {
            sum += getSum(ni.getList(), depth - 1);
        }
    }
    return sum;
}

private int getDepth(List<NestedInteger> nestedList) {
    int depth = 0;
    for (NestedInteger ni : nestedList) {
        if (ni.isInteger()) {
            depth = Math.max(depth, 1);
        } else {
            depth = Math.max(depth, getDepth(ni.getList()) + 1);
        }
    }
    return depth;
}

public int depthSumInverse(List<NestedInteger> nestedList) {
   Queue<NestedInteger> q = new LinkedList(nestedList);
   int prevSum = 0, total = 0;
   while(!q.isEmpty()){
       int size = q.size();
       for(int i = 0; i < size; ++i){
           NestedInteger ni = q.poll();
           if(ni.isInteger()){
               prevSum += ni.getInteger();
           }else{
               q.addAll(ni.getList());
           }
       }
       total += prevSum;
   }
   return total;
}

int[][] dirs = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0 || board[0].length == 0) return false;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, i, j, word.toCharArray(), 0)) return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, int x, int y, char[] word, int index) {
    if (index == word.length)  return true;
    if (index == word.length - 1 && word[index] == board[x][y]) return true;
    if (!inbound(board, x, y)) return false;
    if (word[index] != board[x][y]) return false;
    char curt = board[x][y];
    board[x][y] = '#';
    for (int[] d : dirs) {
        int nx = x + d[0];
        int ny = y + d[1];
        if (inbound(board, nx, ny) && dfs(board, nx, ny, word, index + 1)) {
            return true;
        }
    }
    board[x][y] = curt;
    return false;
}

private boolean inbound(char[][] board, int x, int y) {
    return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
}

directions = [[0,1],[1,0],[-1,0],[0,-1]]
def exist(self, board: List[List[str]], word: str) -> bool:
    m = len(board) 
    n = len(board[0])
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and self.dfs(board, i, j, word, 0):
                return True
    return False
            
def dfs(self, board, x, y, word, index):
    if not self.inbound(board, x, y) or board[x][y] != word[index]:
        return False
    if index == len(word) or (index + 1 == len(word) and word[index] == board[x][y]):
        return True
    temp = board[x][y]
    board[x][y] = '#'
    for dx, dy in self.directions:
        nx = x + dx
        ny = y + dy
        if self.dfs(board, nx, ny, word, index + 1) :
            return True
    board[x][y] = temp
    return False
        
def inbound(self, grid, x, y) :
    return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

Search words on that input String s to find if that set contains a prefix of s. Use memorization to eliminate redundant traversal.

T: O (n^2) S : O (n)

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>();
        dict.addAll(wordDict);
        Map<String, Boolean> memo = new HashMap<>();
        return dfs(s, dict, memo);
    }
    
    private boolean dfs(String s, 
                        Set<String> dict, 
                        Map<String, Boolean> memo) {
        if (dict.contains(s)) return true;
        if (memo.containsKey(s)) return memo.get(s);
        for (int i = 0; i < s.length(); i++) {
            if (dict.contains(s.substring(0, i)) && dfs(s.substring(i), dict, memo)) {
                memo.put(s, true);
                return true;
            }
        }
        memo.put(s, false);
        return false;
    }

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    dic = set(wordDict)
    memo = {}
    return self.dfs(s, dic, memo)
    
def dfs(self, s, dic, memo):
    if s in dic:
        return True
    if s in memo:
        return memo[s]
    for i in range(1, len(s)):
        if s[:i] in dic and self.dfs(s[i:], dic, memo):
            memo[s[i:]] = True
            return True
    memo[s] = False
    return False

Solution2 : dp

Instead of return boolean, carry results.

T: O(n^2 + 2^n + W) W is number of words in the dictionary. S: O(2^n * n + W)

public List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>();
    dict.addAll(wordDict);
    return dfs(s, 0,  dict, new HashMap<Integer, List<String>>());
}

private List<String> dfs(String s, int index, 
    Set<String> dict, HashMap<Integer, List<String>> memo) {
    if (memo.containsKey(index)) return memo.get(index);
    List<String> res = new ArrayList<>();
    if (index == s.length()) {
        res.add("");
        return res;
    }
    for (String prefix : dict) {
        if (s.substring(index).startsWith(prefix)) {
            List<String> next = dfs(s, index + prefix.length(), dict, memo);
            for (String nxt : next) {
                res.add(prefix + (nxt.equals("") ? "" : " ") + nxt);
            }
        }
    }
    memo.put(index, res);
    return res;
}

Build graph from edge. Traverse to see no repeated visited node. Also add count visited nodes to see if it equals n, which means there is no left over nodes.

T: O(n) S: O(n)

int visits = 0;
public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for (int[] e : edges) {
        map.putIfAbsent(e[0], new HashSet<>());
        map.putIfAbsent(e[1], new HashSet<>());
        map.get(e[0]).add(e[1]);
        map.get(e[1]).add(e[0]);
    }
    return dfs(0, -1, new boolean[n], map) && visits == n;
}

private boolean dfs(int curt, int parent, boolean[] visited, Map<Integer, Set<Integer>> map) {
    visited[curt] = true;
    visits++;
    if (map.get(curt) == null) return true;
    for (int next : map.get(curt)) {
        if (next == parent) continue;
        if (visited[next]) return false;
        if (!dfs(next, curt, visited, map)) return false;
    }
    return true;
}

def validTree(self, n: int, edges: List[List[int]]) -> bool:
    if n - 1 != len(edges):
        return False
    graph = [[] for i in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = set()
    return self.dfs(-1, 0, graph, visited) and len(visited) == n
    
def dfs(self, parent, curt, graph, visited):
    if curt in visited:
        return False
    visited.add(curt)
    for nxt in graph[curt]:
        if parent == nxt:
            continue
        if not self.dfs(curt, nxt, graph, visited):
            return False
    return True

This is a weighted edge graph. Construct the graph of the equations and values. Traverse the graph by using DFS or BFS to query result. Starting with 1.0 and cumulate the weight of each traversal.

public double[] calcEquation(List<List<String>> equations,
                             double[] values,
                             List<List<String>> queries) {
    Map<String, Map<String, Double>> map = new HashMap<>();
    for (int i = 0; i < equations.size(); i++) {
        String a = equations.get(i).get(0);
        String b = equations.get(i).get(1);
        map.putIfAbsent(a, new HashMap<>());
        map.putIfAbsent(b, new HashMap<>());
        map.get(a).put(b, values[i]);
        map.get(b).put(a, 1.0 / values[i]);
    }
    double[] res = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        double r = dfs(map,
                new HashSet<>(),
                queries.get(i).get(0),
                queries.get(i).get(1),
                1.0);
        res[i] = r == Double.MAX_VALUE ? -1.0 : r;
    }
    return res;
}

private double dfs(Map<String, Map<String, Double>> map,
                   Set<String> visited,
                   String curt,
                   String target,
                   double curtRes) {
    if (map.get(curt) == null) return Double.MAX_VALUE;
    if (curt.equals(target)) return curtRes;
    visited.add(curt);
    for (String next : map.get(curt).keySet()) {
        if (visited.contains(next)) continue;
        double res = dfs(map, visited, next, target, curtRes * map.get(curt).get(next));
        if (res != Double.MAX_VALUE) {
            return res;
        }
    }
    return Double.MAX_VALUE;
}

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    graph = {}
    for i in range(len(equations)):
        u, v, value = equations[i][0], equations[i][1], values[i]
        if u not in graph:
            graph[u] = []
        graph[u].append([v, value])
        if v not in graph:
            graph[v] = []
        graph[v].append([u, 1 / value])
        
    res = []
    for u, v in queries:
        visited = set()
        res.append(self.dfs(u, v, graph, visited))
    return res

def dfs(self, u, v, graph, visited):
    if u not in graph or u in visited:
        return -1.0
    visited.add(u)
    for nxt, value in graph[u]:
        if nxt == v:
            return value
        res = self.dfs(nxt, v, graph, visited)
        if res != -1.0:
            return res * value
    return -1.0

Backtracking and solve.

public void solveSudoku(char[][] board) {
    if (board == null || board.length == 0){
        return;
    }
    dfs(board);
}

private boolean dfs(char[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') continue;
            for (char c = '1'; c <= '9'; c++) {
                if (isValid(board, i, j, c)) {
                    board[i][j] = c;
                    if (dfs(board)) return true;
                    board[i][j] = '.';
                }
            }
            return false;
        }
    }
    return true;
}

public boolean isValid(char[][] board, int row, int col, char c){
    for(int i = 0; i < 9; i++) {
        if(board[i][col] == c) return false; //check row
        if(board[row][i] == c) return false; //check column
        if(board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
    }
    return true;
}

DFS to get the shortest path. Using Memo. Also cutting branch by only goes in one direction will help to reduce the total paths.

public int minKnightMoves(int x, int y) {
    int[][] memo = new int[301][301];
    for (int[] row : memo) {
        Arrays.fill(row, -1);
    }
    memo[1][2] = 1;
    memo[2][1] = 1;
    memo[0][0] = 0;
    memo[1][1] = 2;
    memo[1][0] = 3;
    memo[2][0] = 2;
    return dfs(x, y, memo);
}

private int dfs(int x, int y, int[][] memo) {
    if (x == 0 && y == 0) {
        return 0;
    }
    if (y > x) {
        int temp = x;
        x = y;
        y = temp;
    }
    x = Math.abs(x);
    y = Math.abs(y);
    if (memo[x][y] != -1) {
        return memo[x][y];
    }
    int res = Math.min(dfs(x - 1, y - 2, memo), dfs(x - 2, y - 1, memo)) + 1;
    memo[x][y] = res;
    return res;
}

public int minDifficulty(int[] jobDifficulty, int d) {
    int n = jobDifficulty.length;
    if (n < d) return -1;
    int[][] cache = new int[n][d + 1];
    for (int[] row : cache) {
        Arrays.fill(row, -1);
    }
    return dfs(jobDifficulty, 0, n, d, cache);
}

private int dfs(int[] nums, int i, int n, int d, int[][] cache) {
    if (cache[i][d] != -1) {
        return cache[i][d];
    }
    if (d == 1) {
        int max = 0;
        while (i < n) {
            max = Math.max(max, nums[i++]);
        }
        return max;
    }
    int res = Integer.MAX_VALUE, maxOnDay = 0;
    for (int j = i; j < n - d + 1; j++) {
        maxOnDay = Math.max(maxOnDay, nums[j]);
        res = Math.min(res, dfs(nums, j + 1, n, d - 1, cache) + maxOnDay);
    }
    cache[i][d] = res;
    return res;
}

Store the longest path from current position x, y in a memo matrix.

int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int[][] memo;
int res = 1;
public int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    memo = new int[m][n];
    for (int[] row : memo) Arrays.fill(row, -1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dfs(i, j, matrix, memo);
        }
    }
    return res;
}

private int dfs(int x, int y, int[][] matrix, int[][] memo) {
    int len = 1;
    for (int[] d : dir) {
        int nx = x + d[0], ny = y + d[1];
        if (inbound(matrix, nx, ny) && matrix[nx][ny] > matrix[x][y]) {
            if (memo[nx][ny] != -1) {
                len = Math.max(len, 1 + memo[nx][ny]);
            } else {
                len = Math.max(len, 1 + dfs(nx, ny, matrix, memo));
            }
        }
    }
    memo[x][y] = len;
    res = Math.max(res, memo[x][y]);
    return len;
}

private boolean inbound(int[][] m, int x, int y) {
    return x >= 0 && y >= 0 && x < m.length && y < m[0].length;
}

public boolean judgePoint24(int[] nums) {
    if (nums == null || nums.length != 4) {
        return false;
    }
    List<Double> list = new ArrayList<>();
    for (int n : nums) list.add((double) n);
    return dfs(list);
}

private boolean dfs(List<Double> list) {
    if (list.size() == 1) {
        return Math.abs(list.get(0) - 24) < 0.001;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        for (int j = i + 1; j < list.size(); j++) {
            for (double d :  compute(list.get(i), list.get(j))) {
                List<Double> nexts = new ArrayList<>();
                nexts.add(d);
                for (int k = 0; k < list.size(); k++) {
                    if (i != k && j != k) {
                        nexts.add(list.get(k));
                    }
                }
                if (dfs(nexts)) return true;
            }
        }
    }
    return false;
}

private List<Double> compute(double a, double b) {
    List<Double> list = new ArrayList<>();
    list.add(a + b);
    list.add(a - b);
    list.add(b - a);
    list.add(a * b);
    if (b != 0) list.add(a / b);
    if (a != 0) list.add(b / a);
    return list;
}

PreviousBFS NextDFS on String

Last updated 3 years ago

Was this helpful?