Blind/Grind 75 Week 4

class Solution {
    // DFS
    // T n; S n
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int curColor = image[sr][sc]; // cur value

        if (curColor == color) {   // nothing change
            return image;
        }

        // DFS
        dfs(sr, sc, curColor, color, image);

        return image;
    }

    private void dfs(int row, int col, int target, int newColor, int[][] image) {
        if (0 <= row && row < image.length && 0 <= col && col < image[0].length ) { // Is valid?
            if (image[row][col] == target) {
                image[row][col] = newColor;
                // Recursion
                dfs(row-1, col, target, newColor, image);
                dfs(row+1, col, target, newColor, image);
                dfs(row, col-1, target, newColor, image);
                dfs(row, col+1, target, newColor, image);
            }
        }
    }
}

import java.util.*;

class Solution {
    // BFS for each 1
    // T n * m
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        
        // Initialize a queue to hold positions of zeros and set length to 0.
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) {
                    q.offer(new int[]{i, j});   // Enqueue all pos of 0
                }
                else mat[i][j] = -1;            // Init 1 to -1 (Unprocessed)
            }
        }
        // Directions ([1,0] [-1,0] [0,1] [0,-1])
        int[] dirX = {1, -1, 0, 0};
        int[] dirY = {0, 0, 1, -1};

        int length = 0;

        // BFS
        while (!q.isEmpty()) {
            int size = q.size();
            length++;   // For each level of BFS, increment length to keep track of distances.
            while (size-- > 0) {
                int[] front = q.poll();
                int r = front[0];
                int c = front[1];
                for (int i = 0; i < 4; i++) {
                    int newRow = r + dirX[i];
                    int newCol = c + dirY[i];
                    // Iter all neighbors
                    if (newRow >= 0 && newCol >= 0 && newRow < n && newCol < m) {
                        if (mat[newRow][newCol] >= 0) continue; // updated/seen
                        mat[newRow][newCol] = length;   // Update the value of the neighbor to length.
                        q.offer(new int[]{newRow, newCol}); // Enqueue the updated neighbor's position. (For Next level)
                    }
                }
            }
        }

        return mat;
    }
}

// End case
if (...) return;

// Iter each elem
for (int x : nums) {
	if (...) continue;    // Skip seen elems
	// Add
	tmp.add(x);
    // Recur
    backtrack(nums, ans, i + 1, tmp);
    // Back
    tmp.remove(tmp.size() - 1);
}

class Solution {
    // Backtrack
    // T nlogn; S nlogn
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(nums, ans, 0, new ArrayList<>());
        return ans;
    }

    private void backtrack(int[] nums, List<List<Integer>> ans, int start, List<Integer> tmp) {
        // End
        if (true) ans.add(new ArrayList<>(tmp));

        // Iter from start to n (lower than start means seen)
        for (int i = start; i < nums.length; i ++) {
            tmp.add(nums[i]);
            // Recur
            backtrack(nums, ans, i + 1, tmp);
            // Back
            tmp.remove(tmp.size() - 1);
        }
    }
}

class Solution {
    // Backtrack
    // T n * n!; S n!
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        // backtrack
        backtrack(ans, new ArrayList<Integer>(), nums);
        return ans;
    }

    private void backtrack(List<List<Integer>> ans, List<Integer> tmp, int[] nums) {
        // if reach the end
        if (tmp.size() == nums.length) {
            ans.add(new ArrayList<Integer>(tmp));   // must deep copy
            return;
        }

        // Traverse each num
        for (int x : nums) {
            if (tmp.contains(x)) continue; // Skip for seen nums
            // Append new num
            tmp.add(x);
            backtrack(ans, tmp, nums);
            // Backtrack: restoring after recursion
            tmp.remove(tmp.size() - 1); // remove last one from seen
        }
    }
}

class Solution {
    // Backtrack
    // T 3^m * 4^n
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) return ans;
        
        // Letters
        String dict[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

        backtrack(ans, digits, new StringBuilder(), dict);
        return ans;
    }

    // The combinations from the first to the last will expand into a recursive tree.
    // The combinations from the first to the last will expand into a recursive tree.
    // When the index reaches the end of digits, we get a combination, and add it to the result, end the current recursion. 
    private void backtrack(List<String> ans, String digits, StringBuilder s, String[] dict) {
        // End
        if (s.length() == digits.length()) {
            ans.add(s.toString());
            return;
        }

        int num = digits.charAt(s.length()) - '0';  // Get the kth char in nums(2-9)
        String letter = dict[num - 2];                  // Get the letters of num
        for (int i = 0; i < letter.length(); i++) {
            s.append(letter.charAt(i));
            // Recur
            backtrack(ans, digits, s, dict);
            // Restore
            s.deleteCharAt(s.length() - 1);
        }

    }
}