Question:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

Thinking:

If we use the recursive way, we should see that the search tree will go down like check [0],[0,1], then [1],[1,2] and [2],[2,3] then [2], [2,3] and [3],[3,4] and [3],[3,4] and [4],[4,5] … There are some nodes are repeated. So we can use interation from bottom to root to store the number of paths in every index of string.

Solution:

public int numDecodings(String s) {
    int l = s.length();
    if (l == 0)    return 0;
    int[] counts = new int[l+1];

    counts[l] = 1;
    if (s.charAt(l-1) != '0')    counts[l-1] = 1;

    for (int i = l-2; i >=0; i--) {
        if (s.charAt(i) == '0')    continue;
        counts[i] = Integer.parseInt(s.substring(i, i+2)) <=26? counts[i+1]+counts[i+2] : counts[i+1];
    }

    return counts[0];
}

Reference: https://leetcode.com/discuss/8527/dp-solution-java-for-reference

Question:

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = “/home/“, => “/home”
path = “/a/./b/../../c/“, => “/c”
click to show corner cases.

Corner Cases:
Did you consider the case where path = “/../“?
In this case, you should return “/“.
Another corner case is the path might contain multiple slashes ‘/‘ together, such as “/home//foo/“.
In this case, you should ignore redundant slashes and return “/home/foo”.

Thinking:

The file system is like a tree, and finding path of this tree is like a dfs process. So we can use stack to track the node of dfs. If the string is “..”, we go back, otherwise go to the given dirctory.

Solution:

public String simplifyPath(String path) {
    Stack<String> stack = new Stack<String>();
    String[] paths = path.split("/");

    for (String p: paths) {
        p = p.trim();
        if (p.equals("") || p.equals("."))    continue;
        if (p.equals(".."))    {
            if (!stack.isEmpty()) {
                stack.pop();
            }
            continue;
        }
        stack.push(p);
    }

    StringBuilder res = new StringBuilder();
    while (!stack.isEmpty()) 
        res.insert(0, "/".concat(stack.pop()));


    return res.length() == 0? "/":res.toString();
}

Question:

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

Thinking:

I assume it’s graph and do dfs in this 2d array. Start from every point and search the result until find the solution or failure. In this process, we need to record the visitied set. In my solution, I used the hashset. But in more efficient way, we can use bit manipulate to mask the visited element.

Solution:

My solution(use HashSet):

public boolean exist(char[][] board, String word) {
    int m = board.length;
    if (m == 0)    return false;
    int n = board[0].length;
    Set<Integer> record = new HashSet<Integer>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (backtracking(board, word, 0, i, j, record))    return true;
    return false;
}

private boolean backtracking(char[][] board, String word, int index, int i, int j, Set<Integer> record) {
    if (board[i][j] == word.charAt(index) && !record.contains(i*board[0].length+j)){
        if (index == word.length()-1)    return true;
        boolean res = false;
        record.add(i*board[0].length+j);
        if (i-1>=0)    res |= backtracking(board, word, index+1, i-1, j, record);
        if (!res && i+1<board.length) res |= backtracking(board, word, index+1, i+1, j, record);
        if (!res && j-1>=0)    res |= backtracking(board, word, index+1, i, j-1, record);
        if (!res && j+1<board[0].length) res |= backtracking(board, word, index+1, i, j+1, record);
        record.remove(i*board[0].length+j);
        return res;
    }
    return false;
}

use the mask:

public boolean exist(char[][] board, String word) {
    char[] w = word.toCharArray();
    for (int y=0; y<board.length; y++) {
        for (int x=0; x<board[y].length; x++) {
            if (exist(board, y, x, w, 0)) return true;
        }
    }
    return false;
}

private boolean exist(char[][] board, int y, int x, char[] word, int i) {
    if (i == word.length) return true;
    if (y<0 || x<0 || y == board.length || x == board[y].length) return false;
    if (board[y][x] != word[i]) return false;
        board[y][x] ^= 256;
    boolean exist = exist(board, y, x+1, word, i+1)
    || exist(board, y, x-1, word, i+1)
    || exist(board, y+1, x, word, i+1)
    || exist(board, y-1, x, word, i+1);
    board[y][x] ^= 256;
    return exist;
}

Question:

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Thinking:

There are four directions can go, move according to the order of right, down, left, up and check the bound of moving.

Solution:

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<Integer>();
    int m = matrix.length;
    if (m == 0)    return res;
    int n = matrix[0].length;
    int direction = 0;//0right, 1down, 2left, 3up
    int i = 0, j = 0;//position
    int c0 = 1, c1 = 1, c2 = 0, c3 = 1;//row and column limit

    while (c0 + c2 - 1 <= n && c1 + c3 - 1 <= m) {
        res.add(matrix[i][j]);
        switch (direction) {
        case 0:
            if (j == n-c0){
                direction = (direction+1) % 4;
                c0++;
                res.remove(res.size()-1);
            }
            else
                j++;
            break;
        case 1:
            if (i == m-c1){
                direction = (direction+1) % 4;
                c1++;
                res.remove(res.size()-1);
            }
            else
                i++;
            break;
        case 2:
            if (j == c2){
                direction = (direction+1) % 4;
                c2++;
                res.remove(res.size()-1);
            }
            else
                j--;
            break;
        case 3:
            if (i == c3){
                direction = (direction+1) % 4;
                c3++;
                res.remove(res.size()-1);
            }
            else
                i--;
            break;
        }
    }
    res.add(matrix[i][j]);

    return res;
}

Question:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Thinking:

Simulate the process of multiplying.

Solution: (Record the result from low digits to high digits in array)

public String multiply(String num1, String num2) {
    int l1 = num1.length(), l2 = num2.length();
    int[] res = new int[l1+l2];

    for (int i = l1-1; i >= 0; i--) {
        for (int j = l2-1; j >= 0; j--){
            int index = l1+l2-i-j-2;
            res[index] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            res[index+1] += res[index] / 10;
            res[index] = res[index] % 10;
        }
    }

    StringBuilder fres = new StringBuilder();
    for (int i = res.length-1; i >= 0; i--)
        if (!(fres.length() == 0 && res[i] == 0))   fres.append(res[i]);

    return fres.length() == 0? "0":fres.toString();
}

A little improvement which record the result from high to low digits in array:

public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] pos = new int[m + n];

for(int i = m - 1; i >= 0; i--) {
    for(int j = n - 1; j >= 0; j--) {
        int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
        int p1 = i + j, p2 = i + j + 1;
        int sum = mul + pos[p2];

        pos[p1] += sum / 10;
        pos[p2] = (sum) % 10;
    }
}  

StringBuilder sb = new StringBuilder();
for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();

}

Reference: https://leetcode.com/discuss/71593/easiest-java-solution-with-graph-explanation