297. Serialize and Deserialize Binary Tree

Difficulty: Medium

Frequency: N/A

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        serializing(root, out);
        return out.str();
    }

    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserializing(in);
    }
private:
    void serializing(TreeNode* root, ostringstream& out) {
        if (root) {
            out << root->val << " ";
            serializing(root->left, out);
            serializing(root->right, out);
        } else out << "# ";
    }
    TreeNode* deserializing(istringstream& in) {
        string val;
        in >> val;
        if (val == "#") return NULL;
        TreeNode *root = new TreeNode(stoi(val));
        root->left = deserializing(in);
        root->right = deserializing(in);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

022. Generate Parentheses

Difficulty: Medium

Frequency: 

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"


My solution:
Data structure:
string, recursive
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> results;
        helper(results, "", n, 0);
        return results;
    }
    void helper(vector<string> &v, string str, int n, int m) {
        if (n == 0 && m == 0) {
            v.push_back(str);
            return;
        }
        if (m > 0) {
            helper(v, str+")", n, m - 1);
        }
        if (n > 0) {
            helper(v, str+"(", n - 1, m + 1);
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

010. Regular Expression Matching

Difficulty: Hard

Frequency: N/A

 

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

My solution:
Data structure:
string
Steps:
1. Check empty input
2. If the second char is not *, check the first char. Continue if they match, or it is .
3. If the second char is *, check whether the t.substr(2) matches s. If not, check whether
    p[0] == ‘.’ or p[0] == s[0].
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p[1] != '*') {
            if(p[0] == s[0] || (p[0] == '.' && s[0] != '\0')) {
                return isMatch(s.substr(1), p.substr(1));
            } else {
                return false;
            }
        } else {
            if (isMatch(s, p.substr(2))) return true;
            int idx = 0;
            while (idx < s.size() && (s[idx] == p[0] || p[0] == '.')) {
                if (isMatch(s.substr(++idx), p.substr(2))) return true;
            }
            return false;
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Need to understand basic regular expression, like .* means zero or more any characters