[leetcode] Combination Sum

vector<vector<int> > findcombination(vector<int> valid, int target){
        vector<vector<int> > res;
        int len = valid.size();
        if(len == 0) return res;
        //discard all the values larger than target.
        while(valid.back() > target){
            valid.pop_back();
            if(valid.empty()) return res;

        }
        int i = valid.size() - 1;
        while( i >= 0 ){
            int head = valid[i];
            int cur = head;
            valid.pop_back();
            vector<int> headvec;
            while(cur <= target){
                headvec.push_back(head);
                if(cur == target){
                    res.push_back(headvec);
                    break;
                }
                vector<vector<int> > tails = findcombination(valid, target - cur);
                for(int j = 0; j < tails.size(); ++j){
                    for(int k = 0; k < headvec.size(); ++k){
                        tails[j].push_back(headvec[k]);
                    }
                    res.push_back(tails[j]);
                }
                cur+=head;
            }
            --i;
        }
        return res;
}

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > res;
        if(candidates.empty()) return res;
        sort(candidates.begin(), candidates.end());
        res = findcombination(candidates, target);
        return res;
    }
=========================================================

    void dfs(int left, vector<int>& candidates, vector<int>& current, vector< vector<int> >& ret, int target) {
        if (!target) {ret.push_back(current); return;}
        for (int i = left; i < (int)candidates.size(); ++ i) {
            if (candidates[i] > target) break;
            current.push_back(candidates[i]);
            dfs(i, candidates, current, ret, target - candidates[i]);
            current.pop_back();
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector< vector<int> > ret;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        dfs(0, candidates, current, ret, target);
        return ret;
    }

[leetcode] Minimum Path Sum *

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

My Code:

 int minPathSum(vector<vector<int> > &grid) {

        if(grid.empty()) return 0;

        int width = grid[0].size();

        int height = grid.size();

        int table[height][width];

        table[0][0] = grid[0][0];

        for(int i = 0; i < height; ++i){

            for(int j = 0; j < width; ++j){

                if(i == 0 && j != 0 )

                    table[0][j] = table[0][j-1]+grid[0][j];

                else if(j == 0 && i != 0)

                    table[i][0] = table[i-1][0]+grid[i][0];

                else if(i != 0 && j != 0){

                    table[i][j] = min(table[i-1][j], table[i][j-1]) + grid[i][j];

                }

            }

        }

        return table[height-1][width-1];

    }

[leetcode] Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

My Code:

 vector<vector<int> > pathSum(TreeNode *root, int sum) {

        vector<vector<int> > res;

        vector<int> path;

        if(!root) return res;

        if(!root->left && !root->right){

            if(root->val == sum){

                path.push_back(root->val);

                res.push_back(path);

                return res;

            }else{

                return res;

            }

        }else{

            if(root->left){

                vector<vector<int> > leftres = pathSum(root->left, sum - (root->val));

                for(int i = 0; i < leftres.size(); ++i){

                leftres[i].insert(leftres[i].begin(), root->val);

                res.push_back(leftres[i]);

                }

            }

            if(root->right){

                vector<vector<int> > rightres = pathSum(root->right, sum - (root->val));

                for(int i = 0; i < rightres.size(); ++i){

                    rightres[i].insert(rightres[i].begin(), root->val);

                    res.push_back(rightres[i]);

                }

            }

            return res;

        }

    }

Discuss

[leetcode] Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

My Code:

 bool hasPathSum(TreeNode *root, int sum) {

        if(!root) return false;

        queue<TreeNode*> q;

        q.push(root);

        while(!q.empty()){

            TreeNode* cur = q.front();

            if(!cur->left && !cur->right){

                if(cur->val == sum)

                    return true;

            }

            else{

                if(cur->left){

                    cur->left->val = cur->val + cur->left->val;

                    q.push(cur->left);

                }

                if(cur->right){

                    cur->right->val = cur->val + cur->right->val;

                    q.push(cur->right);

                }

            }

            q.pop();

        }

        return false;

    }

[leetcode] Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

My Code:

 int sumNumbers(TreeNode *root) {
        if(!root) return 0;
        queue q;
        q.push(root);
        int sum = 0;
        while(!q.empty()){
            TreeNode* cur = q.front();
            if(!cur->left && !cur->right){
                sum = sum + cur->val;
            }
            else{
                if(cur->left){
                    cur->left->val = cur->val*10 + cur->left->val;
                    q.push(cur->left);
                }
                if(cur->right){
                    cur->right->val = cur->val*10 + cur->right->val;
                    q.push(cur->right);
                }
            }
            q.pop();
        }
        return sum;
    }

[leetcode] Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Basic:
Definition of Median:
The median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one (e.g., the median of {3, 3, 5, 9, 11} is 5). If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values (the median of {3, 5, 7, 9} is (5 + 7) / 2 = 6), which corresponds to interpreting the median as the fully trimmed mid-range. 

Algorithm:
This problems seems to be easy, it can be done by O((n+m)log(m+n)) and O((m+n)). However, when it comes to O(log(m+n)), it becomes difficult. We can do this via "find kth largest in a sorted array" and do this separately on odd and even.
1. For odd, just find (m+n)/2 +1 th number. For eve, find (m+n)/2 th and find (m+n)/2+1 th and get the average of these two.
2. For findkth function, we should keep the smaller one as m always and then then it will balanced to be log(m+n).

My Code:

[leetcode] Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Algorithm:

The difference here is that how to handle when A[mid] == A[right]!

then we can not decide the pivot location when A[mid] == A[right]. My solution is that when this happens, just move right to left until A[mid] != A[right].

There may be better solutions, can update later.

My Code:

bool RS(int A[], int left, int right, int target){
        if(right < left) return false;
        if(left == right) {
            if(A[left] == target) return true;
            else return false;
        }
        int mid = (left+right)/2;
        if(A[mid] == target) return true;
        if(A[mid] == A[right]){
            while(A[mid] == A[right] && right >= 0){
                right--;
            }
            return RS(A, left, right, target);
        }
        else if(A[mid] < A[right]){
            // rotated pivot on the left
            if(target < A[mid]) return RS(A, left, mid-1, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        } else {
            //rotated pivot on the right
            if(target > A[mid]) return RS(A, mid+1, right, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        }
    }
bool search(int A[], int n, int target) {
        if(n <= 0) return false;
        return RS(A, 0, n-1, target);
}

[leetcode] Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Algorithm:

1. This can be done by bisection recursion method, the time complexity would be O(logn).

2. The key point is to see if the pivot of the rotation is on the left of mid point or right.

3. Pay attention to the termination of recursion, 1) when left == right and 2) when A[mid] == target.

4. When do recursion, should make (left, mid), and (mid+1, right). Otherwise, it will go to an endless recursion loop.

My code:

int RSearch(int A[], int left, int right, int target){
   if(left == right) {
            if(A[left] == target) return left;
            else return -1;
        }
        int mid = (left+right)/2;
        if(target == A[mid]) return mid;
        if(A[mid] < A[right]){
            // rotated pivot on the left
            if(target < A[mid]) return RSearch(A, left, mid, target);
            else{
              if(target > A[right]) return RSearch(A, left, mid, target);
              else return RSearch(A, mid+1, right, target);
            }
        } else {
            //rotated pivot on the right
            if(target > A[mid]) return RSearch(A, mid+1, right, target);
            else{
              if(target > A[right]) return RSearch(A, left, mid, target);
              else return RSearch(A, mid+1, right, target);
            }
        }
    }
    int search(int A[], int n, int target) {
        if(n <= 0) return -1;
        return RSearch(A, 0, n-1, target);
    }

[leetcode] Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Algorithm.

This is the same as the previous removeDup one. The difference is that, we need to make 

A[cur] = A[cur] - A[cur - 2].

For the next scan, when meet A[j] != 0, means now A[i] = A[i-2] + A[j] and ++i;

My Code:

int removeDuplicates(int A[], int n) {
        if(n < 3) return n;
        for(int cur = n-1; cur > 1; --cur)
            A[cur] = A[cur] - A[cur - 2];
        int i = 2;
        for(int j = 2; j < n; ++j){
            if(A[j]){
                A[i] = A[i-2] + A[j];
                ++i;
            }
        }
        return i;
    }

[Basic Knowledge] Memset, sizeof, Template

1.  memset:
You should include<string.h> if you want use memset.
void memset(void* ptr, int val, size_t num);
    val: unsigned char conversion.
    num: number of bytes.
So, memset can only be used while setting value to zero.

2. sizeof
Yields the size of its operand with respect to the size of type char.

char - 8 bit
byte - 8 bit
int - 32 bit


3. If you want to declare a template function.

template<class TYPE>
void PrintTwice(TYPE data)
{
    cout<<"Twice: " << data * 2 << endl;
}

template<class T1, class T2, class T3>
T2 DoSomething(const T1 tArray[], T2 tDefaultValue, T3& tResult)
{
   ... 
}
For class:
template<class T>
class Item
{
    T Data;
public:
    Item() : Data( T() )
    {}

    void SetData(T nValue)
    {
        Data = nValue;
    }

    T GetData() const
    {
        return Data;
    }

    void PrintData()
    {
        cout << Data;
    }
};
If you want to use Item: Item<int> intitem;

[leetcode] Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Idea:

If use the native idea, it will cost O(n^2) time and constant space. But will lead to time limit exceed. The code is below:

int removeDuplicates(int A[], int n) {
  if(n < 2) return n;
  int i = 0;
  while(i < n - 1){
    int j = i;
    while(A[j] == A[j+1]){
     j++;
    }
    if(j!=i){
      int s = i+1;
      for(int k = j; k < n; k ++){
        A[s] = A[k];
        s++;
      }
      n = n - (j-i);
    }
    i++;
  }
  return n;
}

============================================================================

Then I changed to another method and it passed the tests: Time complexity is O(n)

1. make each value in the array = current val - previous val;(This part need to be done from the end.)

2. find zeros and change that to valid values.

 int removeDuplicates(int A[], int n) {
       if(n < 2) return n;
       for(int cur = n-1; cur > 0; --cur) 
          A[cur] -= A[cur-1];
       int i = 1;
       for (int j = 1; j < n; ++ j)
        if (A[j]) {
            A[i] = A[i - 1] + A[j];
            ++ i;
        }
       return i;
    }

[leetcode] Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

This problem took me 2 hours to finish. At first, I was thinking this in a DP way, but failed. Then I used two pointers: start and end. The key is when to move start and when to move end.

1. when the current sum value <= 0,  move start. 1) if end is positive, move start to end, else move start to end+1.

2. when current sum value > 0, keep start and move end backwards, as this sub-array would give positive contribution.

My Code :

 int maxSubArray(int A[], int n) {
        int s = 0, e = 0;
        int curval = 0, maxval = INT_MIN;
        int maxs = 0, maxe = 0;
        while(e < n){
            curval = curval + A[e];
            if(curval > maxval){
                maxval = curval;
                maxs = s;
                maxe = e;
            }
            if(curval < 0){
                if(A[e] > 0){
                    s = e;
                    e = s;
                } else{
                    s = e + 1;
                    e = s;
                }
                curval = 0;
            } else {
                e = e + 1;
            }
        }
        return maxval;
    }

=============However, the divide and conquer result is still not finished!=======

[leetcode] Word Break II

Dynamic Programming give a lower bound for the Recursion. Even though do the pruning, it won't be faster than Dynamic Programming!!!

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

The first try is time limit exceed with input as:

string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";

["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"]
My Code:

 vector wordBreak(string s, unordered_set &dict) {
        vector pos;
        vector res;
        if(dict.empty()) return res;
        int n = s.length();
        if(s.empty()){
            res.push_back(" ");
            return res;
        }
        for(int len = 1; len <= n; len++){
            if(dict.find(s.substr(0, len)) != dict.end())
                pos.push_back(len);
        }
        for(int i = 0; i < pos.size(); i++){
            vector curp = wordBreak(s.substr(pos[i], n - pos[i] + 1), dict);
            if(curp.empty()) continue;
            else{
                for(int j = 0; j < curp.size(); j++){
                    string curs = s.substr(0, pos[i]) + " " + curp[j];
                    res.push_back(curs);
                }
            }
        }
        return res;
}

================================================================================

Then I used wordbreak test on WordBreak I to pruning. When there is no valid word break, do the pruning.

 bool wordCheck(string s, unordered_set &dict) {
        if(s.empty() || dict.empty()) return false;
        int n = s.length();             
        bool table[n];              
        memset(table, 0, sizeof(table));                   
        for(int i = 0; i < n; i ++){
            if(dict.find(s.substr(0, i+1)) != dict.end()) {
                table[i] = true;
                continue;
            }
            for(int j = 0; j < i ; j++){
                if(table[j] && dict.find(s.substr(j+1, i-j)) != dict.end()){            
                    table[i] = true;
                    break;
                }
            }
        }
        return table[n-1];
    }                                                              
  vector wB(string s, unordered_set &dict) {         
        vector res;
        if(dict.empty()) return res;
        int n = s.length(); 

                                       
        if(s.empty()){                                             
            res.push_back(" ");                                    
            return res;
        }                                                          
        // Pruning!!!!! The order is important!!!
        if(!wordCheck(s, dict)) return res;
        for(int len = 1; len <= n; len++){
            vector curp;
            if(dict.find(s.substr(0, len)) != dict.end())
                curp = wB(s.substr(len, n - len + 1), dict);
            
                if(curp.empty()) continue;
                else{
                  for(int j = 0; j < curp.size(); j++){
                    string curs = s.substr(0, len) + " " + curp[j];
                    res.push_back(curs);
                  }
                }
        }
    return res;
  }
  vector wordBreak(string s, unordered_set &dict){
    vector res = wB(s, dict);                              
    for(int i = res.size()-1; i>=0; --i){                          
        while(res[i].back() == ' ')
            res[i].erase(res[i].size()-1);
    }
    return res;

  }

[leetcode] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code"

This problem is easy while using Dynamic Programming. The first time I tried was failed. If you find the existed words in sequence the following data should be failed:
s = "aaaaaaa"
dict = ["aaa", "aaaa"]. Because what you found would be aaa aaa a and return a false. 

Algorithm:
1. Find the problem and subproblem and their relations.
2. Build a table[n][n], and table[0][n] would be the result we return.
3. table[i][j] = true iff s.substr(i, j-i+1) is in the dict OR for every i<=k<=j, 
   table[i][k]&&table[k+1][j] is true.

Tips:
while your final result is depend on table[0][n], you should make length as the out-most loop control.

My Code:
bool wordBreak(string s, unordered_set<string> &dict) {
        int n = s.length();
        bool table[n][n];
        memset(table, 0, sizeof(table));
        for(int len = 0; len < n; len++){
            for(int i = 0; i < n-len; i++){
                int j = i + len;
                table[i][j] = (dict.find(s.substr(i, j-i+1)) == dict.end() ? false:true);
                if(!table[i][j]){
                    for(int k = i; k < j; k++){
                        if(table[i][k] && table[k+1][j]){
                        table[i][j] = true;
                        break;
                        }
                    }
                }
            }
        }
        return table[0][n-1];
    }

=============================================================================

Better Solution with O(n^2) space and time complexity.

My code:

 bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.empty() || dict.empty()) return false;
        int n = s.length();
        bool table[n];
        memset(table, 0, sizeof(table));
        for(int i = 0; i < n; i ++){
            if(dict.find(s.substr(0, i+1)) != dict.end()) {
                table[i] = true;
                continue;
            }
            for(int j = 0; j < i ; j++){
                if(table[j] && dict.find(s.substr(j+1, i-j)) != dict.end()){
                    table[i] = true;
                    break;
                }
            }
        }
        return table[n-1];
    }

[leetcode] Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Algorithm:

Using the previous method to have an previous pointer in the node will lead to memory limit exceed.

1. Use a map<string, vector<string>> to maintain the previous string list.

2. Use two unordered_set curlev and nxtlev to expand the tree.

3. the output from start to end can be done by recursion nicely.

My Code:

 map<string, vector<string>> mp;

    vector<string> path;

    vector<vector<string>> res;

public:

    void findDict(string str, unordered_set<string> &dict, unordered_set<string> &nxtlev){

        //find the next level strings in the dict and add them in nxtlev

        if(str.empty() || dict.empty()) return;

        string cur;

        for(int i = 0; i < str.length(); ++i){

            cur = str;

            for(char j = 'a'; j <= 'z'; ++j){

                cur[i] = j;

                if(dict.find(cur) != dict.end()){

                    // add str to cur's path list.

                    // update the nxtlev.

                    mp[cur].push_back(str);

                    nxtlev.insert(cur);

                }

            }

        }

    }

    void output(string start, string end){

        if(start == end){

            reverse(path.begin(), path.end());

            res.push_back(path);

            reverse(path.begin(), path.end());

        }

        else{

            for(int i = 0; i < mp[end].size(); i++){

                path.push_back(mp[end][i]);

                output(start, mp[end][i]);

                //need to pop the back out and get the new one in the same level.

                path.pop_back();

            }

        }

    }

    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {

        mp.clear();

        path.clear();

        res.clear();

        //add start and end to the dictionary.

        dict.insert(start);

        dict.insert(end);

        unordered_set<string> curlev;

        curlev.insert(start);

        unordered_set<string> nxtlev;

        path.push_back(end);

    

        while(true){

            for(auto it = curlev.begin(); it != curlev.end(); ++it){

                dict.erase(*it);

            }

            for(auto it = curlev.begin(); it != curlev.end(); ++it){

                findDict(*it, dict, nxtlev);

            }

            if(nxtlev.empty()) return res;

            if(nxtlev.find(end) != nxtlev.end()){

                output(start, end);

                return res;

            }

            curlev.clear();

            curlev = nxtlev;

            nxtlev.clear();

        }

    }

[leetcode] Word Ladder I

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Basic Stuff:

This is a good question that I learnt a lot.

1. The unordered_set<xxx> is a good data structure that hold dictionary. It is similar as hashtable but not exactly the same. Insert(), find(), remove() can be done in constant time. 

2. If you can do bi-directional search, Bi-BFS is a great way to use for this problem.

Algorithm:

1. The basic idea for this problem is to build  a tree structure. Start from the start string, find the qualified next strings in the dictionary and then do the same thing on those strings. 

2. We can do a BFS on the tree as we need the shortest path. 

3. As we can also search from the end, we could use the Bi-directional BFS to get that while they meet at some point. This would make the search time to n/2

4. The truth is that when we find the meeting point, it should both on the lowest level of the start tree and also the lowest level of the end tree. 

5. The right level should be the be-found tree's front() + opposite direction tree's end().

My Code:

bool valid(string start, string end){                             
        if(start.length() != end.length()) return false;          
        int count = 0;
        for(int i = 0; i < start.length(); ++i){                  
            if(start[i]!=end[i]){                                 
                count++;
                if(count > 1) return false;
            }
        }
        return true;
}

vector FindinDict(string source, unordered_set &dict){ 
   vector ret;
   if(source.empty() || dict.empty()) return ret;
   for(int i = 0; i < source.length(); i++){
       string curs = source;
       for(char j = 'a'; j <='z'; j++){
           curs[i] = j;
           auto fd = dict.find(curs);
           if(fd != dict.end()){
               ret.push_back(*fd);
           }
       }
   }
   return ret;
}

struct node{
   string str;
   int lev;
   node(string s, int l){str = s; lev = l;}
};

int ladderLength(string start, string end, unordered_set &dict) {
   if(valid(start, end)) return 2;
   queue sq;
   queue eq;
   map svisited;
   map evisited;

// Should initialize the maps.
   for(auto it = dict.begin(); it != dict.end(); ++it){
        svisited[*it] = false;
        evisited[*it] = false;
   }
  sq.push(node(start,1));
  eq.push(node(end,1));
  svisited[start] = true;
  evisited[end] = true;
  int slevel = 1;
  int elevel = 1;

// Here use the queue size to control the expand of each tree. But still expand 

// level by level
  while(!sq.empty() && !eq.empty()){
    if(sq.size() < eq.size()){
        while(!sq.empty() && sq.front().lev == slevel){
            vector snxt = FindinDict(sq.front().str, dict);
            for(auto it = snxt.begin(); it != snxt.end(); ++it){
                if(!svisited[*it]) {
                    sq.push(node(*it, slevel+1));

                    // When to set the visited true is crucial in BFS.
                    svisited[*it] = true;
                }
                if(evisited[*it]) return (sq.front().lev+eq.back().lev);
            }
            sq.pop();
        }
        slevel++;
     }
    else{
        while(!eq.empty() && eq.front().lev == elevel){
            vector enxt = FindinDict(eq.front().str, dict);
            for(auto it = enxt.begin(); it != enxt.end(); ++it){
                if(!evisited[*it]) {
                    eq.push(node(*it, elevel+1));
                    evisited[*it] = true;
                }
                if(svisited[*it]) return (eq.front().lev + sq.back().lev);
            }
            eq.pop();
        }
      elevel++;
    }
  }
  return 0;
}

[leetcode] Tree Traversal

1. preorder traversal
Previously I did the preorder traversal the same way as inorder traversal, however, there is a more simplified way to do that.

vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ret;
        if(!root) return ret;
        stack s;
        s.push(root);
        while(!s.empty()){
            TreeNode* cur = s.top(); s.pop();
            ret.push_back(cur->val);
            if(cur->right) s.push(cur->right);
            if(cur->left) s.push(cur->left);
        }
        return ret;
    }

[leetcode] word search

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 =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
This is almost the same as the question I met before while interviewed by Google for the last round. However, still a little bit difference. Will talk about this later.
Algorithm:
1. For search board problem, it is convenient to use recursion to solve the problem.
2. pay attention to the termination of recursion. The order of the termination matters.
3. easy-to-messed-up details are coloured red in the code.
4. Should set the visited back to false if the current visit is not validate.
Attention:
Firstly got wrong on passing the 2D array of visited, the way I test correctly now is to use a ** pointer and set the value first separately.
My code:

bool searchword(vector> &board, int h, int w, int i, int j, 
                    string word, int wordpos, bool **visited){
         if(wordpos == word.length()) return true;
         if(i < 0 || i > h-1 || j < 0 || j > w-1) return false;
         if(board[i][j] != word[wordpos] || visited[i][j] == true) return false;
         visited[i][j] = true;
         if(searchword(board, h, w, i+1, j, word, wordpos+1, visited)) 
           return true;
         if(searchword(board, h, w, i-1, j, word, wordpos+1, visited)) 
           return true;
         if(searchword(board, h, w, i, j+1, word, wordpos+1, visited)) 
           return true;
         if(searchword(board, h, w, i, j-1, word, wordpos+1, visited)) 
           return true;
         visited[i][j] = false;
         return false;
        }
    bool exist(vector > &board, string word) {
        if(word.empty()) return false;
        if(board.empty()) return false;
        int h = board.size();
        int w = board[0].size();
        bool **visited;
        visited = new bool *[h];
        for(int i = 0; i < h; i++)
            visited[i] = new bool[w];
        for(int i = 0; i < h; i++)
          for(int j = 0; j < w; j++)
            visited[i][j] = false;
        for(int i = 0;i < h; i++){
            for(int j = 0; j < w; j++){
                if(board[i][j] == word[0]){
                    if(searchword(board, h, w, i, j, word, 0, visited))
                        return true;
                }
            }
        }
        return false;
    }