Day 36, 71,73 Simplify Path, Set Matrix Zeroes

Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
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".

 -------------------------------------------------
Solution #1, using stack
'/' skip
'.' ignore/continue
'..' pop stack

class Solution {
public:
    string simplifyPath(string path) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i=0;
        stack<string> s;
        while (i < path.length()) {
            while (path[i] == '/' && i < path.length()) { // skip '/'
                 i++;
            }
            if (i == path.length())  break; // if string ends wiht '/'
            int start = i;
            while (path[i] != '/' && i < path.length()) { // get end point of sub path
                i++;
            }
            string elem = path.substr(start,i - start);
            if (elem == ".") {
                continue;
            }
            if (elem == "..") {
                if (!s.empty()) {
                    s.pop();
                }
                continue;
            }
            s.push(elem);
        }
        if (s.empty()) {
            return "/";
        }
        string ret;
        while (!s.empty()) {
            string temp = "/" + s.top();
            ret = temp + ret; 
            s.pop();
        }
        return ret;
    }
};

Solution #2, using two/three pointers
to be continued
  
Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

---------------------------------------
Solution #1, O(m+n) space 

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> row(m,false);
        vector<bool> col(n,false);
        if (m != 1 || n != 1) {
            // find 0
            for (int i=0;i<m;i++) {
                for (int j=0;j<n;j++) {
                    if (matrix[i][j] == 0) {
                        row[i] = true; 
                        col[j] = true;
                    }
                }
            }
            // set to 0
            for (int i=0;i<m;i++) {
                for (int j=0;j<n;j++) {
                    if (row[i] || col[j]) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }
};

Solution #2, in space
instead of allocating two vectors, using the first row and column to store the zero row/col

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool rowZero = false, colZero = false;
        int rows = matrix.size();
        int cols = matrix[0].size();
        // check first row
        for (int i=0;i<cols;i++) {
            if (matrix[0][i] == 0) {
                rowZero = true;
            }
        }
        // check first column
        for (int i=0;i<rows;i++) {
            if (matrix[i][0] == 0) {
                colZero = true;
            }
        }
        
        for (int i=1;i<rows;i++) {
            for (int j=1;j<cols;j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        for (int i=1;i<rows;i++) {
            for (int j=1;j<cols;j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // if first row has 0
        if (rowZero) {
            for (int i=0;i<cols;i++) {
                matrix[0][i] = 0;
            }
        }
        // if first col has 0
        if (colZero) {
            for (int i=0;i<rows;i++) {
                matrix[i][0] = 0;
            }
        }
    }
};