Valid Number

Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

class Solution {//pass both large and small
        //the most complete number has the pattern below, and the sections are named accordingly:
        //-123.45e-67
        //s1
        //  d1
        //    p
        //     d2
        //       e
        //        s2
        //          d3
    struct Status{
        int s1;//first sign
        int d1;//digit
        int p;//point
        int d2;//after point, before e
        int s2;//second sign
        int e;//exponential sign
        int d3;//after e
        int sum(){return d1+d2+d3+p+e+s1+s2;}
    };
    bool isDigit(const char c){
        return (c <= '9' && c >= '0');
    }
public:
    bool isNumber(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        while(*s == ' ') ++s;//heading ' ' 
        if (!*s) return false;//empty
        
        Status r;
        r.d1 = r.d2 = r.d3 = 0;
        r.p = 0;
        r.e = 0;
        r.s1 = r.s2 = 0;
        
        const int S1 = 1;//1
        const int D1 = S1*2;//2
        const int P = D1*2;//4
        const int D2 = P*2;//8
        const int E = D2*2;//16
        const int S2 = E*2;//32
        const int D3 = S2*2;//64
        //think the numbers as a bit map
        
        while(*s != ' ' && *s != '\0'){//major loop
            switch(*s){
                case '.':
                    if (r.p || r.e) return false;
                    if (!r.s1) r.s1 = S1;
                    r.p = P;
                break;
                
                case '+':
                case '-':
                    if (r.s2 || r.d3 ) return false;
                    else if(r.s1){ 
                        if (!r.e) return false;//.-4
                        else r.s2 = S2;}
                    else r.s1 = S1;
                break;
                    
                case 'e':
                    if (r.e || r.s2) return false;
                    r.s1 = S1;//mark the defaul sign
                    r.e = E;
                break;
                
                default:
                    if (!isDigit(*s)) return false;
                    if (!r.s1) r.s1 =S1;//default sign
                    if (r.e) r.d3 = D3;
                    else if(r.p) {r.d2 = D2;}
                    else r.d1 = D1;
                    if (r.d3) r.s2 = S2;
            }
            ++s;
        }

        while(*s == ' ') ++s;//tailing ' '
        if (*s) return false;//empty
        
        int sum  = r.sum();
        switch(sum){
            case D1://123
            case S1+D1://+123, -123
            case D1+P://123.
            case P+D2://.12
            case S1+D1+P://-123.
            case S1+P+D2://-.12
            case D1+P+D2://123.3
            case S1+D1+P+D2://-123.3
            
            case D1+E+S2+D3://123
            case S1+D1+E+S2+D3://+123, -123
            case D1+P+E+S2+D3://123.
            case P+D2+E+S2+D3://.12
            case S1+D1+P+E+S2+D3://-123.
            case S1+P+D2+E+S2+D3://-.12
            case D1+P+D2+E+S2+D3://123.3

            case S1+D1+P+D2+E+S2+D3://-123.3e-45

                return true;
        }
        return false;
    }
};

Valid Parentheses

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

class Solution {
public:
    bool isValid(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stack<char> v;
        for(int ii = 0; ii < s.length(); ++ii){
            switch(s[ii]){
                case '{':
                case '[':
                case '(':
                    v.push(s[ii]);
                    break;
                case '}':
                case ']':
                case ')':
                    if (v.empty()) return false;
                    char c = v.top();//expect {[(
                    if (c+1 == s[ii] || c+2 == s[ii]) v.pop();//ASCII
                    else return false;
            }
        }
        return v.empty();
    }
};

Valid Sudoku

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

class Solution {
    bool validate(vector<char> &num){
        vector<bool> v(10,false);
        for(int ii = 0; ii < num.size(); ++ii){
            if (num[ii] == '.') continue;
            int index = num[ii] - '0';
            if (v[index]) return false;
            else (v[index] = true);
        }
        return true;
    }
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        for(int ii = 0; ii < board.size(); ++ii){
            if (!validate(board[ii])) return false;
        }
        
        for(int col = 0; col < board.size(); ++col){
            vector<char> v;
            for(int row = 0; row < board.size(); ++row){
                v.push_back(board[row][col]);
            }
            if (!validate(v)) return false;
        }
        
        for(int start = 0; start < 3; ++start){
            for(int first = 0; first < 3; ++first){
                vector<char> block;
                for(int line = 0; line < 3; ++line){
                    for(int cell = 0; cell < 3; ++cell){
                        int row = start * 3 + line;
                        int col = first * 3 + cell;
                        block.push_back(board[row][col]);
                    }
                }
                if (!validate(block)) return false;
            }
        }
        return true;
    }
};

Validate Binary Search Tree

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<int> v;
    void inOrder(TreeNode *root){
        if (!root) return;
        inOrder(root->left);
        v.push_back(root->val);
        inOrder(root->right);
        return;
    }
public:
    bool isValidBST(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        v.clear();
        inOrder(root);
        for(int ii = 1; ii < v.size(); ++ii){
            if (v[ii] <= v[ii-1]) return false;
        }
        return true;
    }
};

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

First Solution is recursive. Good for concept, but not efficient enough to pass large test sets:

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (*p == '*'){//return true;
            while(*p == '*') ++p;
            if (*p == '\0') return true;
            while(*s != '\0' && !isMatch(s,p)){
                ++s;                
            }
            return *s != '\0';
        }
        else if (*p == '\0' || *s == '\0') return *p == *s;
        else if (*p == *s || *p == '?') return isMatch(++s,++p);
        else return false;
    }
};

Dynamic Programming, iteration version, both time and memory efficient:

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!*s && !*p) return true;
        
        int ms_max = 1;//size of *s
        const char* ss = s;
        while(*ss){ ++ms_max;++ss;}
        int np_max = 1;
        const char* pp = p;
        while(*pp){if(*pp!='*')++np_max;++pp;}
        if(ms_max < np_max) return false;
        
        vector<vector<bool> > r(2, vector<bool>(ms_max, false));
        bool flag = 1;
        r[0][0] = true;
        do{//*p
            int ms = 1;
            ss = s;
            if (*p == '*'){
                while(*p == '*') ++p;
                --p;
                r[flag][0] = r[!flag][0];
                for( ;ms <= ms_max; ++ms){//up and left
                    if (r[!flag][ms] || r[flag][ms-1]) break;
                    else r[flag][ms] = false;
                }
                for(;ms <= ms_max; ++ms){
                    r[flag][ms] = true;
                }
            }
            else{
                do{
                    bool r_flag = false;
                    if (*ss == *p || *p == '?'){
                        r_flag = r[!flag][ms-1];//diagnal
                    }
                    r[flag][ms]=r_flag;
                    ++ms;++ss;
                }while(*ss);//*s
                r[flag][0] = false;
            }
            ++p;
            flag = !flag;
        }while(*p);
        return r[!flag][ms_max-1];
    }
};

The thinking process:

The recursive method is intuitive and gives great insight of the matching process. If we neglect the boundary cases for a moment, there are three basic cases when we try to match the characters in s[] and p[]:
1.  No match. Simply return false. This is the last case in the program.
2. Single match. Either *s == *p, or *p == '?'. The return value of this case depends on the result of the rest parts of both s[] and p[] (recursion call), which start at the 'diagonal' position by advancing both s[] and p[] by 1 (++s, ++p)
3. Star case, i.e. when *p == '*'. This is where the complication comes in. A star can match 0, 1, 2, ..., to the end of string s[].  So, as long as one of the substrings match (recursion call), after advance over *, it returns true. This case returns false only after exhausting all possible substrings without a match.

After we have some sense on the dependencies of each step, learned from the recursive function calls, we can set up our dynamic programming frame. For example s[] = "abcdef" and p[] = "a?c*f"

The  strings are indexed 1 for convenience. Now let's directly apply the rules learned from the recursion method:

The arrow means "depends on" or "recursion call". The cells without a match can be pre-filled with FALSE's. The tail cell '\0' '\0' is marked TRUE.

We eventually want to know cell(0,0), but we have to know cell(1)first;
s[1] == p[1] gives case 2, so cell(1) depends on cell(2);
p[2] == '?' gives case 2, so cell(2) depends on cell(3);
s[3] == p[3] gives case 2, so cell(3) depends on cell(4);
p[4] == '*' gives case 3, so cell(4) depends on all the crimson shaded cells. As long as one of the shaded cells is TRUE, Cell(4) is TRUE.
...
p[5] == s[6] gives case 2, so cell(5) depends on the tail '\0','\0' case, which is TRUE. So cell(5) = TRUE.
Then we trackback, just as the recursive functions.
cell(0) = cell(1) = cell(2) = cell(3) = cell(4) = cell(5) = TRUE.
At last the function returns TRUE.

The steps above is using dynamic programming matrix, but follow the recursion process. Now we do the REAL dynamic programming. Note that the problem is symmetric, which means you can match the strings from left to right, or from right to left, they are identical. In the recursion method, the actual result propagates from the bottom right corner to the up left corner. In dynamic programming, we want to start with row one, so we can flip the whole dependency graph. Again the arrows mean dependencies, or get value from.

All the non-matching cells are pre-filled with FALSE's. The only initial TRUE is at cell(0), which is also the case when you match two NULL strings. So now you just need a matrix size(s)*size(p), and fill the cells row by row according to the three rules:
1. No matching: fill FALSE;
2. Matching, or '?': copy the value from previous diagonal cell
3. '*': Look up all cells to the left, and look up the cells to the left of previous row, and the cell directly above ---- if there is at least one TRUE, fill TURE; otherwise fill FALSE

Finally return the value of the last cell.

There are some more tricks in practice.
Firstly, successive '*' is equivalent to a single '*', so we may suppress them together. After doing this, the number of '*'s is at most size(p)/2. So the worst run time is O(m*n + m^2), where m=size(p) and n=size(s).
Also consider that after removing all '*'s, size(p) <= size(s), which means m is at most 2n for the worst case, so that m = O(n). Thus the worst run time is O(m*n).

Secondly, the matrix is updated row by row, and even the '*' case requires two latest rows. So it is possible to have a space efficient way solve the matching problem by using two size(s) arrays.