Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Note: See the previous wrong answers

class Solution {
public:
    int minCut(string s) {
        int slen=s.size();
       
        if (slen<=1) return 0;
        vector<int> minc(slen+1,0);
        for (int i=0; i<slen+1; i++)
        {
            minc[i]=i-1;
        }
       
        for (int i=0; i<slen; i++)
        {
            for (int j=0; i-j>=0&&i+j<slen&&s[i-j]==s[i+j]; j++)
            {
                minc[i+j+1]=min(minc[i+j+1],minc[i-j]+1);
            }
           
            for (int j=1; i-j+1>=0&&i+j<slen&&s[i-j+1]==s[i+j]; j++)
            {
                minc[i+j+1]=min(minc[i+j+1],minc[i-j+1]+1);
            }
        }
       
        return minc[slen];
    }
};

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

 https://oj.leetcode.com/discuss/13336/shortest-o-n-dp-solution-with-explanations

The key is to use a vector of 256 int to be hashmap and use i-startIdx+1 to denote the length of the string.

从左往右扫描，当遇到重复字母时，以上一个重复字母的index+1，作为新的搜索起始位置，

直到最后一个字母，复杂度是O(n)。

 

 

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len=s.length();
       
        vector<int> v(256,-1);
        int ret=0, startIdx=0;
       
        for (int i=0; i<len; i++)
        {
            int j=s[i];
            startIdx = max(v[j]+1,startIdx);
            v[j]=i;
            ret = max(ret,i-startIdx+1);
        }
       
        return ret;
    }
};

Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Idea: scan twice: find out the inversion and

correct the number of candies for the corresponding child.

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n= ratings.size();
        if (n==0)  return 0;
        int total=0;
        vector<int> res(n,1);
        for (int i=1; i<n; i++)
        {
            if (ratings[i]>ratings[i-1])
            {
                res[i]=res[i-1]+1;
            }
        }
       
        for (int i=n-2; i>=0; i--)
        {
            if (ratings[i]>ratings[i+1]&&res[i]<=res[i+1])
            {
                res[i]=res[i+1]+1;
            }
        }
       
        for (int j=0; j<n; j++)
        {
           total+=res[j];
        }   
       
        return total;
    }
};

Best Time to Buy and Sell Stock III

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Idea:

A very helpful discussion from
https://oj.leetcode.com/discuss/1381/any-solutions-better-than-o-n-2
'
First consider the case that when we are only allowed to make one transaction. we can handle this easily with DP. If we move forward, any new price we meet will only affect our history result by two ways:
will it be so low that it beats our previous lowest price? will it be so high that we should instead sell on this time to gain a higher profit (than the history record)? Similarly, we can move backward with the highest price and profit in record. Either way would take O(n) time. Now consider the two transaction case. Since there will be no overlaps, we are actually dividing the whole time into two intervals.??
We want to maximize the profit in each of them so the same method above will apply here. We are actually trying to break the day at each time instance, by adding the potential max profit before and after it together. By recording history and future for each time point, we can again do this within O(n) time.'


class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n=prices.size();
        if (n<2) return 0;
       
        int low=prices[0], hi=prices[n-1];
        vector<int> profit1(n,0);
        vector<int> profit2(n,0);
       
        for(int i=1; i<n; i++)
        {
            low = min(low, prices[i]);
            profit1[i]=max(prices[i]-low,profit1[i-1]);
        }
       
        for (int j=n-1; j>=0; j--)
        {
            hi = max( hi, prices[j]);
            profit2[j]=max(hi-prices[j],profit2[j]);
        }
       
        int maxProfit=0;
        for (int i=0; i<n;i++)
        {
            maxProfit = max(maxProfit, profit1[i]+profit2[i]);
        }
        return maxProfit;
    }
};

Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Idea: greedy method

My thought is to slide the window of minIdx and maxIdx. Another solution is much more concise.
1.
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n=prices.size();
       
        if(n<2)
           return 0;
          
        int minp=prices[0], maxp=prices[1];
        int minIdx=0, maxIdx=1;
        int maxProfit = maxp-minp;
        for (int i=1; i<n; i++)
        {
            if (prices[i]<minp)
               {
                   minp=prices[i];
                   minIdx = i;
                   if (minIdx>=maxIdx)
                   {
                    maxp=prices[i];
                    maxIdx=i;                  
                   }
               }
            if (prices[i]>maxp)
                {
                    maxp=prices[i];
                    maxIdx=i;
                }
            int tmp = maxp-minp;
            if(tmp>maxProfit)
              {
                  maxProfit=tmp;
              }
        }
       
        return maxProfit;
    }
};

2.

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n=prices.size();
       
        if(n<2)
           return 0;
          
        int minp=prices[0],maxProfit = 0;
        for (int i=1; i<n; i++)
        {
            maxProfit = max(maxProfit, prices[i]-minp);
            minp=min(prices[i],minp);
        }
       
        return maxProfit;
    }
};

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)


https://oj.leetcode.com/discuss/422/is-there-better-solution-for-jump-game-ii?start=0#a_list_title

'The idea is to use "last" to keep track of the maximum distance that has been reached by using the minimum steps "ret", whereas "curr" is the maximum distance that can be reached by using "ret+1" steps.  curr = max(i+A[i]) where 0 <= i <= last.'

class Solution {
public:
    int jump(int A[], int n) {
       
        int ret=0,last=0,cur=0;
       
        for (int i=0;i<n; i++)
        {
            if (i>last)
            {
                if (cur==last&&last<n-1)
                   return -1;
               
                last=cur;
                ret++;
            }
           
            cur = max(cur,i+A[i]);
        }
        return ret;
    }
};

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

1. O(N) time complexity and O(1) space complexity

class Solution {
public:
    bool canJump(int A[], int n) {
       
        int maxdist=0;
       
        for (int i=0; i<=maxdist&&i<n;i++)
        {
            maxdist = max(maxdist, i+A[i]);
        }
       
        return maxdist>=n-1;
    }
};

2. My original solution. O(N^2) time complexity

class Solution {
public:
    bool canJump(int A[], int n) {
        int i=0;
        int j=0;
        int newI, newJ;
        while(j<n-1)
        {
            j=i+A[i];
            if(j>=n-1)
              return true;
            int nextMax=j+A[j];
            newI=j;
            for (int k=i; k<j; k++)
            {
                if (k+A[k]>nextMax)
                {
                    nextMax=k+A[k];
                    newI = k;
                }
            }
           
            i=newI;
            if (nextMax==j)
               return false;
        }
       
        return true;
    }
};

sqrt(int x)

Implement int sqrt(int x).
Compute and return the square root of x.

http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots


1. Newton method

class Solution {
public:
    int sqrt(int x) {
        double a = double(x);
        double r=1;
        double res;
       
        while(1)
        {
            res=0.5*(r+a/r);
            if (abs(res-r)<1e-10)
               break;
            r=res;
        }
       
        return int(res);
    }
};

2. Binary search: The int is rounded to lower.
a. Remember to use division instead of multiplication.
b. low+1<hi
c. hi=mid; low=mid

class Solution {
public:
    int sqrt(int x) {
        if (x<=1) return x;
       
        int mid =1, low=1, hi=x;
       
        while (low+1<hi)
        {
            mid=low+(hi-low)/2;
            if (mid==x/mid)
               return mid;
            else if (mid>x/mid)
            {
                hi=mid;
               
            }
            else
            {
                low=mid;
            }
        }
        return low;
    }
};

Pow(x, n)

Implement pow(x, n).

This one seems easy, but one needs to be very careful to code it right. Esp. remember to deal with the fact that n could be negative!

1. Iterative way:
class Solution {
public:
    double pow(double x, int n) {
         if (n==0) return 1;
         double ret=1;
         int m=n;
         for (;n!=0;x=x*x,n=n/2)
         {
             if (n%2!=0)
                ret*=x;
         }
        
         if (m<0)
           ret=1/ret;
        
         return ret;
    }
};

2. Recursive way:
class Solution {
public:
    double pow(double x, int n) {
         if (n<0)
           return 1/power(x,-n);
         else
           return power(x,n);
    }
   
    double power(double x, int n)
    {
        if (n==0) return 1;
       
        double v=power(x,n/2);
       
        if (n%2==0)
           return v*v;
        else
           return v*v*x;
    }
};

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Draw a picture and visualize it:

11111222           
          222
Let's say x is the distance from head of the linked list to the entry node where the cycle begins, a is the distance from entry node where the cycle begins to the node where the slow and fast pointers meet, r is the size of the loop. s is the distance where slow pointer has travelled before slow point and fast pointer have met. L is the length from meet point to entry point.

2*s=s+nr;
s = nr;
x+a=nr=(n-1)*r + r = (n-1)*r + L-x;

x=(n-1)*r + L-x-a;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head==NULL||head->next==NULL)
           return NULL;
        ListNode *p1=head;
        ListNode *p2=head;
       
        while(p1!=NULL&&p2!=NULL)
        {
            p1=p1->next;
            p2=p2->next==NULL?NULL:p2->next->next;
           
            if (p1==p2)
            {
                p2=head;
                while(p1!=p2)
                {
                    p1=p1->next;
                    p2=p2->next;
                }
                return p1;
            }
        }
       
        return NULL;
    }
};

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.


class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        int row = board.size();
        int col = board[0].size();
        vector<vector<bool> > visited(row, vector<bool>(col,false));
       
        for (int r=0; r<row; r++)
        {
            for (int c=0; c<col; c++)
            {
               if (helper(board,word,r,c, row, col,0, visited))
                   return true;              
            }
        }
       
        return false;
    }
    bool helper(vector<vector<char>> &b, string word, int r, int c, int row, int col, int i, vector<vector<bool>> &visited)
    {
        if (i==word.length())
            return true;
           
        if (r>=row || r<0 || c<0 || c>=col)   
           return false;
          
        if (visited[r][c])
            return false;
       
        if (b[r][c]!=word[i])
            return false;
       
        visited[r][c] = true;

        //find neighbors if there are valid ones
        bool ret= helper(b,word,r+1,c,row,col, i+1, visited)||helper(b,word,r-1,c,row,col,i+1,visited)
               || helper(b,word,r, c+1, row, col, i+1,visited) ||helper(b,word,r,c-1,row,col,i+1,visited);
   
        visited[r][c]=false;
       
        return ret;
    }
};

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

 

 

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        int r=board.size();
        if (r==0) return;
        int c=board[0].size();
        if (c==0) return;
        solve(board,r,c);
   
    }
   
    bool valid(vector<vector<char> > &board,int x, int y, int t,  int r, int c)
    {
        //check col, rows
        for (int i=0; i<r; i++)
        {
            if (board[i][y]==board[x][y]&&i!=x)
                return false;
        }
       
        for (int j=0; j<c; j++)
        {
            if (board[x][j]==board[x][y]&&j!=y)
               return false;
        }
       
        int regionX = (x/3)*3;
        int regionY = (y/3)*3;
       
        for (int i=regionX; i<regionX+3; i++)
        {
            for (int j=regionY; j<regionY+3; j++)
            {
                if (board[i][j]==board[x][y]&&((i!=x)||(j!=y)))
                   return false;
            }
        }
        return true;
    }
   
    bool solve(vector<vector<char> > &board, int r, int c)
    {
        for (int x=0; x<r; x++)
        {
            for (int y=0; y<c; y++)
            {
                if (board[x][y]=='.')
                {
                    for (int i=0; i<9; i++)
                    {
                        board[x][y] = '1'+i;
                        if (valid(board,x,y,i,r,c)&&solve(board,r,c))
                           {
                               return true;
                           }
                        board[x][y]='.';
                    }
                    return false;
                }
            }
        }
        return true;
    }
};

Generate Parentheses

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:
"((()))", "(()())", "(())()", "()(())", "()()()"

Solving this recursively can lead to a good and concise code. Though DP can be used to solve it too.

1. Recursive way
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string r;
        stack<string> st;
        dfs(res,r,0,0,n);
        return res;
    }
   
    void dfs(vector<string> &res, string r, int leftCount, int rightCount,int n)
    {
        if (leftCount==n&&rightCount==n)
        {
            res.push_back(r);
            return;
        }
        else
        {
            if (leftCount<n)
            {
                dfs(res,r+"(",leftCount+1,rightCount,n);
            }
           
            if (rightCount<leftCount)
            {
                dfs(res,r+")",leftCount,rightCount+1,n);
            }
        }
       
    }
};

2. DP

Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Backtracking. Solution 1 is faster than solution 2.


Solution 1:

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int>> res;
        int n=num.size();
        sort(num.begin(), num.end());
        if (n==0||num[0]>target)
           return res;
        vector<int> r;
        vector<int> prev;
        dfs(num, res,r, 0, target,0);
        return res;
    }
   
    void dfs(vector<int> &n, vector<vector<int>> &res, vector<int> &r, int sum, int t, int start)
    {
        if (sum==t)
        {
            res.push_back(r);
            return;
        }
        else
        {
            int ns=n.size();
            int previous = -1;
            for (int i=start; i<ns; i++)
            {
                if (n[i]+sum>t)
                   return;
                if (previous==n[i]) continue;
                previous = n[i];
                r.push_back(n[i]);
                dfs(n,res,r,sum+n[i],t,i+1);
                r.pop_back();
            }
        }
    }
};

Solution 2:
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int>> res;
        int n=num.size();
        sort(num.begin(), num.end());
        if (n==0||num[0]>target)
           return res;
        vector<int> r;
        vector<int> prev;
        dfs(num, res,r, 0, target,0);
        return res;
    }
   
    void dfs(vector<int> &n, vector<vector<int>> &res, vector<int> &r, int sum, int t, int start)
    {
        if (sum==t)
        {
            for (int i=0; i<res.size(); i++)
            {
                if (res[i]==r)
                  return;
            }
            res.push_back(r);
            return;
        }
        else
        {
            int ns=n.size();
            for (int i=start; i<ns; i++)
            {
                if (n[i]+sum>t)
                   return;
                r.push_back(n[i]);
                dfs(n,res,r,sum+n[i],t,i+1);
                r.pop_back();
            }
        }
    }
};

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Backtracking:

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> res;
        int n=candidates.size();
        sort(candidates.begin(),candidates.end());
        if (n==0||candidates[0]>target)
           return res;
        vector<int> r;
       
        dfs(res,candidates,target,0, r, 0);
        return res;
    }
   
    void dfs(vector<vector<int>> &res, vector<int> &cs, int t, int sum, vector<int> &r, int idx)
    {
        if (sum==t)
        {
            res.push_back(r);
        }
        else
        {
            int n=cs.size();
            for (int i=idx; i<n; i++)
            {
                if (sum+cs[i]>t)
                    return;
                r.push_back(cs[i]);
                dfs(res,cs,t,sum+cs[i],r,i);      //pay attention to this
                r.pop_back();
            }
        }
       
    }
};

Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

I know it's backtracking, but this problem is harder than I had thought to code it right and I don't quite understand the second solution.

Answer 1:
class Solution {
public:
    bool valid(string s)
    {
        int n=s.size();
        int v = atoi(s.c_str());
        if (n==3&(v==0||v>255)) return false;
        if (n==2&&(v==0||s[0]=='0')) return false;
        if (n==3&&(s[0]=='0')) return false;
        return true;
    }
    void  dfs(vector<string> &res, string s, string ip, int k)
    {
        if (k==0)
        {
            if (s.empty())
            {
                res.push_back(ip);
            }
            return;
        }
        else
        {
            for (int i=1; i<=3; i++)
            {
                if (s.size()>=i&&valid(s.substr(0,i)))
                {
                    if (k==1)
                       dfs(res,s.substr(i),ip+s.substr(0,i),k-1);
                    else
                       dfs(res,s.substr(i),ip+s.substr(0,i)+".", k-1);
                }
            }
           
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        dfs(res,s,"",4);
        return res;
    }
};


Answer2 :

class Solution {
public:
 void dfs(string s, int start, int step, string ip, vector<string>& result)
 {
     int n=s.size();
     if (start==n &&step==4)
     {
         ip.erase(ip.size()-1);
         result.push_back(ip);
         return;
     }
    
     if (n-start>(4-step)*3)
         return;
     if (n-start<4-step)
         return;
        
     int num=0;
    
     for (int i=start; i<start+3&&i<n; i++)
     {
         num=num*10+(s[i]-'0');
        
         if (num<=255){
             ip+=s[i];
             dfs(s,i+1,step+1,ip+'.', result);
         }
         if (num==0) break;
     }
    
    }
 vector<string> restoreIpAddresses(string s) {
     vector<string> result;
     string ip;
    
     dfs(s,0,0,ip,result);
     return result;
 }
};

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<int>> r;
        vector<int> t;
        dfs(r,n,t);
        int num=r.size();
        vector<vector<string>> result;
       
        for (int i=0; i<num; i++)
        {
            vector<string> tmp;
            for (int j=0; j<n; j++)
            {
                string t(n,'.');
                t[r[i][j]]='Q';
                tmp.push_back(t);
            }
            result.push_back(tmp);
        }
       
        return result;
    }

    bool isvalid(int i, vector<int> &r)
    {
        //
        int s = r.size();
       
        for (int j=0; j<s; j++)
        {
            if (r[j]==i || r[j]-i==j-s ||r[j]-i==s-j )  //Pay attention to here
               return false;
        }
       
        return true;
    }
    void dfs(vector<vector<int>> &r, int n, vector<int> &t)
    {
        if (t.size()==n)
        {
            r.push_back(t);  //There's no r.clear();
        }
        else
        {
            for (int i=0; i<n; i++)
            {
                if (isvalid(i,t))
                {
                    t.push_back(i);
                    dfs(r,n,t);
                    t.pop_back();  //backtracking
                }
            }
        }
    }
};

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

There are several approaches to this problem.

1. Recursion:
The code is the simplest but quite slow.

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m<1||n<1) return 0;
        if (m==1&&n==1) return 1;
       
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }
};

2. Math:
In total the robot should walk m + n - 2 steps, m - 1 steps to right and n - 1 steps to bottom,  so we need to select which m - 1 steps to be right, or which n-1 steps to bottom. The problem is actually a combination problem. We just need to calculate (n + m - 2)! / ((m - 1)! * (n - 1)!).

The tricky part to code is to avoid overflow when m and n are big.
a. Calculate (n+m-2)*(n+m-2-1)*(n+m-2-2)*..*max(m,n)
b. Use type long long instead of int when calculating the factorial

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m<1||n<1) return 0;
        if (m==1&&n==1) return 1;
       
        int max = std::max(m,n)-1;
        int min = std::min(m,n)-1;
       
        int r = int(factorial(max+min,max+1)/(factorial(min,1)));
        return r;
    }
   
    long long factorial(int x,int start)
    {
        long long r=1;
        for (int i=x;i>=start; i--)
        {
            r=r*i;
        }
        return r;
    }
};

A more concise implementation:
class Solution {
    public:
        int uniquePaths(int m, int n) {
            int N = n + m - 2;// how much steps we need to do
            int k = m - 1; // number of steps that need to go down
            double res = 1;
            // here we calculate the total possible path number
            // Combination(N, k) = Combination(N, N - k)
            for (int i = 1; i <= k; i++)
                res = res * (N - k + i) / i;
            return (int)res;
        }
    };

3. DP

class Solution {
public:
    int uniquePaths(int m, int n) {
       vector<int> f(n,0);
       f[0]=1;
      
       for (int i=0; i<m; i++)
       {
           for (int j=1;j<n;j++)
           {
               f[j]=f[j-1]+f[j];
           }
       }
      
       return f[n-1];
    }
};

Dynamic Programming

My understanding of dynamic programming is to store values to avoid recursion. This will improve the running time of an algorithm from exponential to linear.

Here's some excerpts I read from the book Algorithms in C++ : parts 1 - 4 : fundamentals : data structures : sorting : searching

1. Bottom-up DP:
    Instead of recursively call the functions and get the result Rn, we get Rn by computing all the function values in order starting at the smallest, using previously computed values at each step to compute the current value Rc.

2. Top-down DP:
    An even simpler view of the technique that allows us to execute recursive functions at the same cost as ( or less cost than) bottom-up DP in an automatic way.
    We instrument the recursive program to save each value that it computes (as its final action, ie at the next to last line of the recursive function ), and to check the saved values to avoid recomputing any of them (as its first action, ie, in the first line of the previously recursive function). It's also sometimes called memorization.

We can use bottom-up DP any time that we use the top-down DP, although we need to make sure that we compute the function values in an appropriate order, so that each value we need has been computed when we need it.

In top-down DP, we save known values. In bottom-up DP, we precompute them. We generally prefer top-down to bottom-up DP for:

1. It's a mechanical transformation of a natural problem solution. (Less code change)
2. The order of computing the subproblems takes care of itself
3. We may not need to compute answers to all the subproblems.

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Initial attempt:
class Solution {
public:
    bool palindrome(string s)  
    {
        int len = s.size();
        for (int i=0;i<len/2; i++)
        {
            if (s[i]!=s[len-i])
              return false;
        }
        return true;
    }
   
    void helper( int i, string s, vector<string> &p, vector<vector<string>> &ret)
    {
        int slen = s.size();
        if (i==slen-1&&flag)
        {
            ret.push_back(p);
        }
       
   
        for (int k=i; k<slen; k++)
        {
            if (palindrome(s.substr(0,k)))
               {
                   p.push_back(s.substr(0,k));       //Got stuck
               }
        }
        i++;
    }
   
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        int len=s.size();
        if (len==0) return ret;
       
        vector<string> p;
        helper(0,s,p,ret);
        return ret;
    }
};

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Idea:
Use BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        int row = board.size();
        if (row<=1) return;
        int col = board[0].size();
        if (col<=1) return;
        for (int c=0; c<col; c=c+col-1)
        for (int r=0; r<row; r++)
         {
             if (board[r][c]=='O')
                findBdCoords(board,r, c, row, col);
         }
       
        for (int r=0; r<row; r=r+row-1)
        for (int c=0; c<col; c++)
        {
             if (board[r][c]=='O')
                findBdCoords(board,r, c, row, col);           
        }
        for (int r=0; r<row; r++)
        for (int c=0; c<col; c++)
        {
             if (board[r][c]=='O')
                   board[r][c]='X';
             if (board[r][c]=='B')
                 board[r][c]='O';
        }      
    }
    void findBdCoords(vector<vector<char>> &board, int r, int c, int row, int col)
    {
        if (board[r][c]!='B')
            board[r][c]='B';
        queue<pair<int,int>> q;
        q.push(make_pair(r,c));
       
        while(!q.empty())
        {
           //4 directions neighbor
           pair<int,int> cur = q.front();
           q.pop();
          
           r = cur.first, c = cur.second;
           pair<int, int> neis[4]={{r+1,c},{r-1,c},{r,c+1},{r,c-1}};
          
           for (int i=0; i<4; i++)
           {
               int rt = neis[i].first, ct = neis[i].second;
               if (rt>=0&&ct>=0&&rt<row&&ct<col&&board[rt][ct]=='O')
               {
                   q.push(make_pair(rt,ct));     
                    board[rt][ct]='B';               
               }
           }
        }
    }
};

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.

The solution is quite long and can be divided to several parts:


class Solution {
public:
void calAdj(const string s, unordered_set<string> & dict, unordered_set<string>& adjset){
     adjset.clear();
     for( int i = 0; i < s.size(); i++){
         string tmp(s);
         for( char az = 'a'; az <= 'z'; az++){
             tmp[i] = az;
             if( dict.find(tmp) != dict.end()){ //tmp is in dictionary
                 adjset.insert(tmp);
             }
         }
     }
}
void pathreverse(unordered_map<string, unordered_set<string>>& pathmap, string start, vector<vector<string>>& pathlist){
     vector<string> & lastpath = pathlist[pathlist.size()-1];
     lastpath.push_back( start );
     vector<string> prepath(lastpath);
     int p = 0;
     for( auto nstr : pathmap[start] ){
          if( p > 0 )//generate new path
              pathlist.push_back(prepath);
          pathreverse(pathmap, nstr, pathlist);
          p++;
     }
}
vector< vector<string> > findLadders(string start, string end, unordered_set<string> &dict){
      vector< vector<string> > pathlist;
      string tmp = start;
      start = end;
      end = tmp;
      int slen = start.size();
      int elen = end.size();
      if( slen != elen )
          return pathlist;
      dict.insert(start);
      dict.insert(end);
      //run bfs
      unordered_map<string, unordered_set<string>> pathmap;
      unordered_set<string> curset;
      curset.insert(start);
      dict.erase(start);
      unordered_set<string> adjset;
      bool find = false;
      while( !find && curset.size() > 0 ){
           unordered_set<string> preset(curset);
           curset.clear();
           for( auto pres : preset){
                if( pres == end ){//find it
                    find = true;
                    pathlist.push_back(vector<string>());
                    pathreverse(pathmap, end, pathlist);
                    break;
                }
                calAdj(pres, dict, adjset);
                curset.insert(adjset.begin(),adjset.end());//put in next layer
                for( auto nexts : adjset ){
                     pathmap[nexts].insert(pres); // record its parents
                }
           }
           for( auto vs : curset) // remove visited string
                dict.erase(vs);
      }
      return pathlist;
}
};