Walls and Gates -- LeetCode 286

[Question]

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

[Analysis]
DFS starting from each gate,  each visited room store the minimum distance. It is also possible to use BFS.

[Solution]
void walls_and_gates (vector<vector<int>>& grid) {
    for (int i=0; i<grid.size(); i++)
        for(int j=0; j<grid[0].size(); j++)
            if (grid[i][j]==0) dfs(grid, i, j, 0);
    return;
}

void dfs (vector<vector<int>>& grid, int i, int j, int dist) {
    if (i>=grid.size() || i<0 || j<0 || j>=grid[0].size() || grid[i][j]<dist) return;
    grid[i][j] = dist;
    dfs(grid, i+1, j, dist+1);
    dfs(grid, i, j+1, dist+1);
    dfs(grid, i-1, j, dist+1);
    dfs(grid, i, j-1, dist+1);
}

Verify Preorder Serialization of a Binary Tree -- LeetCode 331

[Question]

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where #represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing nullpointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

[Analysis]
There are two approaches, using stack or using recursion.

1) When scan the string backward (from the end), push "#" into stack. When non-"#" appears, there must be at least two "#" in the stack. Then pop up two "#" and push one "#" into stack -- that means one valid sub-tree is found. Then repeat the process until entire string is done. The stack should contain only one "#".

2) Scan the string forward. For each sub-tree (starting from a non-"#'), the rest string should be able to be split into two valid sub-trees (left, right).

[Solution]
//-- backward and using a stack --
class Solution {
public:
    bool isValidSerialization(string preorder) {
        reverse(preorder.begin(), preorder.end() );
        stringstream ss(preorder);
       
        string s;
        stack<string> st;
        while (getline(ss, s, ',')) {
            if (s.compare("#") == 0) st.push("#");
            else {
                if (st.size()<2) return false;
                st.pop();  // pop up 2 "#" and push 1 "#"
            }
        }
        return st.size()==1 && st.top().compare("#")==0;
    }
};

//-- recursion --
class Solution {
    bool validate( string & str ) {
        if (str.empty()) return false;
     
        int end = str.find(',');
        if (end==string::npos) return false;
     
        string s = str.substr(0, end);
        str = str.substr(end+1);
     
        if (s.compare("#") == 0) return true;
        if (!validate(str)) return false;
        if (!validate(str)) return false;
        return true;
    }
 
public:
    bool isValidSerialization(string preorder) {
        string data = preorder +",";
        return validate( data ) && data.empty();
    }
};