Misc

Set Matrix Zeroes

note that, the key to this problem is to devise a constant space solution. So the basic idea is to use first row and column to record some information.

class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;

        boolean row = false, col = false;
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < n; ++i) {
            if (matrix[0][i] == 0) {
                row = true;
            }
        }
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) {
                col = true;
            }              
        }

        // deal with right-bottom rectangle 
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // reprocess based on first row and first col
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // deal with first row 
        if (row) {
            for (int i = 0; i < n; ++i) {
                matrix[0][i] = 0;
            }
        }

        // deal with first col
        if (col) {
            for (int i = 0; i < m; ++i) {
                matrix[i][0] = 0;
            }
        }
    }
}

Rotate Image

The idea was firstly transpose the matrix and then flip it symmetrically. For instance,

1  2  3             
4  5  6
7  8  9

after transpose, it will be swap(matrix[i][j], matrix[j][i])

1  4  7
2  5  8
3  6  9

Then flip the matrix horizontally. (swap(matrix[i][j], matrix[i][matrix.length-1-j])

7  4  1
8  5  2
9  6  3

the code is the following:

class Solution {
    public void rotate(int[][] matrix) {
        // transpose the matrix
        // swap matrix[i][j] to matrix[j][i]
        for (int i = 0; i < matrix.length; ++i) {
            for (int j = i; j < matrix[0].length; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // flip the matrix horizontally 
        for (int i = 0; i < matrix.length; ++i) {
            for (int j = 0; j < matrix[0].length / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][matrix[0].length - 1 - j];
                matrix[i][matrix[0].length - 1 - j] = temp;
            }
        }
    }
}

Spiral Matrix

the key is to keep one total variable and four direction variables. Inside the while loop, we will walk around a cycle.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;

        int n = matrix.length;
        int m = matrix[0].length;

        int top = 0, bottom = n - 1, left = 0, right = m - 1;
        int total = n * m;

        while (total > 0) {
            if (bottom >= top) {
                for (int i = left; i <= right; ++i) {
                    res.add(matrix[top][i]);
                    total--;
                }
                top++;
            }
            if (total > 0 && left <= right) {
                for (int i = top; i <= bottom; ++i) {
                    res.add(matrix[i][right]);
                    total--;
                }
                right--;
            }
            if (total > 0 && bottom >= top) {
                for (int i = right; i >= left; --i) {
                    res.add(matrix[bottom][i]);
                    total--;
                }
                bottom--;
            }
            if (total > 0 && left <= right) {
                for (int i = bottom; i >= top; --i) {
                    res.add(matrix[i][left]);
                    total--;
                }
                left++;
            }
        }
        return res;
    }
}

Letter Combinations of a Phone number

the key is how to represent the char table, use 2D array or use map?

another thing that need to notice is that how to use StringBuilder more efficiently.

the stand way to use StringBuilder in dfs is like this

for (...)
    sb.append(...);
    dfs();
    sb.deleteCharAt(sb.length() - 1);

another thing is define 2D array, the number of columns in different row can be different. like this example, table[0].length = 3, and table[5].length = 4;

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;

        char[][] table = {{'a', 'b', 'c'}, 
                          {'d', 'e', 'f'},
                          {'g', 'h', 'i'},
                          {'j', 'k', 'l'},
                          {'m', 'n', 'o'},
                          {'p', 'q', 'r', 's'},
                          {'t', 'u', 'v'},
                          {'w', 'x', 'y', 'z'}};

        dfs(res, digits, 0, table, new StringBuilder());
        return res;
    }

    private void dfs(List<String> res, String s, int i, char[][] table, StringBuilder sb) {
        if (i == s.length()) {
            res.add(sb.toString());
            return;
        }

        for (char c : table[s.charAt(i) - '0' - 2]) {
            sb.append(c);
            dfs(res, s, i + 1, table, sb);
            sb.deleteCharAt(sb.length() - 1);
        }        
    }
}