Leetcode: Longest Valid Parentheses in C++

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution:
int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        int maxv = 0;
        for(int i = n-2; i>=0;i--)
        {
            if(s[i]=='(')
            {
                int j = i+ dp[i+1]+1;
                if(j<n&&s[j]==')')
                dp[i] = 2 + dp[i+1] + dp[j+1];
                maxv = max(dp[i], maxv);
            }
        }
        return maxv;
    }

Leetcode: Next Permutation in Java

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1


Solution:
public void nextPermutation(int[] num) {
        int size = num.length-1;
        if(size<=0)
            return;
        int nonorder = 0;
        int tmp = 0;
        while(size>0&&num[size]<=num[size-1])
        {
            size--;
        }
        nonorder = size;
        if(nonorder>0)
        {
            nonorder--;
            size = num.length-1;
            while(size>=0&&num[size]<=num[nonorder])
            {
                size--;
            }
            tmp = num[size];
            num[size] = num[nonorder];
            num[nonorder] = tmp;
            nonorder++;
        }
        size =  num.length-1;
        while(nonorder<size)
        {
            tmp = num[size];
            num[size] = num[nonorder];
            num[nonorder] = tmp;
            nonorder++;
            size--;
        }
    }

Leetcode: Letter Combinations of a Phone Number in C++

Given a digit string, return all possible letter combinations that the number could represent.
Solution:
vector<char> switchchar(char input)
    {
    vector<char> result;
switch(input)
{
case '2':
result.push_back('a');
result.push_back('b');
result.push_back('c');
break;
case '3':
result.push_back('d');
result.push_back('e');
result.push_back('f');
break;
case '4':
result.push_back('g');
result.push_back('h');
result.push_back('i');
break;
case '5':
result.push_back('j');
result.push_back('k');
result.push_back('l');
break;
case '6':
result.push_back('m');
result.push_back('n');
result.push_back('o');
break;
case '7':
result.push_back('p');
result.push_back('q');
result.push_back('r');
result.push_back('s');
break;
case '8':
result.push_back('t');
result.push_back('u');
result.push_back('v');
break;
case '9':
result.push_back('w');
result.push_back('x');
result.push_back('y');
result.push_back('z');
break;
   }
   return result;
    }
    void helper(string digits, string cur, int num, vector<string>& result )
    {
        if(num==digits.size())
        {
            result.push_back(cur);
        }
        char digit = digits[num];
        vector<char> option = switchchar(digit);
        for(int i=0;i<option.size();i++)
        {
            helper(digits, cur+option[i], num+1, result);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        string cur = "";
        helper(digits, cur, 0, result);
        return result;
    }

Leetcode: Minimum Path Sum in C++

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.Solution：

First Version:void helper(vector<vector<int> > &grid, int m, int n, int& max, int cur)    {        if(m<=grid.size()-1&&n<=grid[0].size()-1)        {            cur+=grid[m][n];            if(m==grid.size()-1&&n==grid[0].size()-1&&cur<max)            max = cur;            helper(grid, m, n+1, max, cur);            helper(grid, m+1, n, max,cur);        }        else            return;    }    int minPathSum(vector<vector<int> > &grid) {        int max = INT_MAX;        if(grid.size()==0)        return 0;        int cur = 0;        helper(grid, 0,0,max,cur);        return max;    }

Second Version:

int minPathSum(vector<vector<int> > &grid) {
        if(grid.size()==0)
        return 0;
        int row = grid.size();
        int column = grid[0].size();
        vector<int> cur(column, INT_MAX);
        cur[0] = 0;
        for(int i=0;i<row;i++)
        {
            cur[0] = cur[0]+grid[i][0];
            for(int j=1;j<column;j++)
            {
                cur[j] = min(cur[j], cur[j-1])+grid[i][j];
            }
        }
        return cur[column-1];
    }

Leetcode: Generate Parentheses in C++

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:

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

void help(int n, int left, int right, string cur,vector<string>& result )
    {
        string tmp;
        if(right==n)
        result.push_back(cur);
        if(left<n)
        {
            tmp=cur+"(";
            help(n, left+1, right, tmp, result);
        }
        if(left>right)
        {
            tmp = cur+")";
            help(n, left, right+1, tmp, result);
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string cur = "";
        help(n, 0, 0, cur, result);
        return result;
    }

Leetcode: Combination Sum II in C++

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.

A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6] 

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 

Solution:
void helper(vector<vector<int> > &result,vector<int> current, int target,vector<int> &candidates, int i )
    {
        if(target<0)
        return;
        if(target==0)
        {
            result.push_back(current);
            return;
        }
        if(i < candidates.size())
        {
            int count =1;
            while(i+1<candidates.size()&&candidates[i]==candidates[i+1])
            {
                count++;
                i++;
            }
            helper(result, current, target, candidates, i+1); 
            while(count>0)
            {
                current.push_back(candidates[i]);
                target -= candidates[i];
                helper(result, current, target, candidates, i+1); 
                count--;
            }
               
        }
        return;
    }
    vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int> > result;
        vector<int> current;
        helper(result, current, target, candidates, 0);
        return result;
    }

Leetcode: Combination Sum in C++

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.

A solution set is:
[7]
[2, 2, 3] 

For example, given candidate set 2,3,6,7 and target 7, 

Solution:

void helper(vector<vector<int> > &result,vector<int> current, int target,vector<int> &candidates, int i )
    {
        if(target<0)
        return;
        if(target==0)
        {
            result.push_back(current);
            return;
        }
        if(i < candidates.size())
        {
            helper(result, current, target, candidates, i+1); 
            int t = target;
            while(t>=0)
            {
                current.push_back(candidates[i]);
                t = t- candidates[i];
                helper(result, current, t, candidates, i+1);
            }
        }
        return;
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int> > result;
        vector<int> current;
        helper(result, current, target, candidates, 0);
        return result;
    }

Leetcode: Edit Distance in C++

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution:

int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > inner(m+1,vector<int>(n+1, 0));
        for(int i=0;i<=m;i++)
        {
            inner[i][0] = i;//word2 is empty
        }
        for(int i=0;i<=n;i++)
        {
            inner[0][i] = i; //word1 is empty
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(word1[i-1] == word2[j-1])
                {
                    inner[i][j] = inner[i-1][j-1];
                }
                else
                {
                    int ins = inner[i][j-1]+1; //insert
                    int del = inner[i-1][j]+1;  //delete
                    int rep = inner[i-1][j-1]+1; //replace
                    inner[i][j] = min(ins, min(del, rep));
                }
            }
        }
        return inner[m][n];
    }

Leetcode: Climbing Stairs in C++

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution:
int climb(int n, vector<int>& ways)
    {
        if(n<0)
        return 0;
        if(ways[n]==-1)
        {
            ways[n] = climb(n-1, ways)+climb(n-2, ways);
            return ways[n];
        }
        else
            return ways[n];
    }
    int climbStairs(int n) {
        if(n==0)
        return 1;
        if(n<0)
        return 0;
        vector<int> ways(n+1,-1);
        ways[0]=1;
        return climb(n, ways);
    }

Leetcode: Unique Paths II in C++

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]

The total number of unique paths is 2.

Solution:

int help(int m, int n, vector<vector<int> >& obstacleGrid, vector<vector<int> >& result)
    {
        if(result[m][n]!=-1)
        {
            return result[m][n];
        }
        result[m][n] = 0;
        if(obstacleGrid[m-1][n-1]==1)
        {
            return 0;
        }
        if(m>1)
        result[m][n] += help(m-1,n,obstacleGrid, result);
        if(n>1)
        result[m][n] += help(m,n-1,obstacleGrid ,result);
        return result[m][n];
    }
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        if(obstacleGrid.size()==0)
        return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int> > result(m+1, vector<int>(n+1, -1));
        if(obstacleGrid[0][0]==0)
        {
            result[1][1] =  1;
        }
        else
            result[1][1] =  0;
        help(m, n, obstacleGrid, result);
        return result[m][n];
    }

Leetcode: Unique Paths in C++

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?

Solution:

int help(int m, int n, vector<vector<int> >& result)
    {
        if(result[m][n]!=-1)
        {
            return result[m][n];
        }
        result[m][n] = 0;    
        if(m>1)
        result[m][n] += help(m-1,n,result);
        if(n>1)
        result[m][n] += help(m,n-1,result);
        return result[m][n];
    }
    int uniquePaths(int m, int n) {
        vector<vector<int> > result(m+1, vector<int>(n+1, -1));
        result[1][1] = 1;
        help(m, n, result);
        return result[m][n];
    }

Leetcode: Word Search in C++

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.
Solution:
4 direction DFS search
bool search(vector<vector<char> > &board, string word, int pos, int x, int y,vector<vector<bool> >& mark)
    {
        if(pos==word.size())
        return true;
        if(x<0||y<0||x>=board.size()||y>=board[0].size())
        return false;
        if(board[x][y]!=word[pos]||mark[x][y]==true)
        return false;
        else
        {
            mark[x][y]=true;
            return search(board, word, pos+1, x+1 , y, mark)||search(board, word, pos+1, x-1 , y, mark)||search(board, word, pos+1, x , y+1, mark)||search(board, word, pos+1, x , y-1, mark);
        }
    }
    bool exist(vector<vector<char> > &board, string word) {
        int len = word.size();
        
        int pos = 0;
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(board[i][j] == word[pos])
                {
                    vector<vector<bool> > mark(board.size(),vector<bool>(board[0].size(),false));
                    if(search(board, word, pos, i , j, mark))
                    return true;
                }
            }
        }
        return false;
    }

Leetcode: Decode Ways in C++

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Solution: 

int numDecodings(string s) {
         if(s.size() == 0)
            return 0;
        vector<int> ways(s.size() + 1,0);
        ways[s.size()] =1;
        for(int i = s.size() - 1; i >= 0; --i)
        {
            //one digit number
            if(s[i] == '0')
                ways[i] = 0;
            else
                ways[i] = ways[i+1];
            
            //two digit number
            if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
                ways[i] += ways[i + 2];
            }
        }
        return ways[0];
    }

Leetcode: Unique Binary Search Trees II in C++

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

vector<TreeNode *> generate(int start, int end)
    {
        vector<TreeNode *> result;
        if(start>end)
        {
            result.push_back(NULL);
            return result;
        }
        for(int i=start;i<=end;i++)
        {
            vector<TreeNode *> leftsub = generate(start, i-1);
            vector<TreeNode *> rightsub = generate(i+1,end);
            for(int m=0;m<leftsub.size();m++)
            {
                for(int n=0;n<rightsub.size();n++)
                {
                    TreeNode* root = new TreeNode(i);
                    root->left = leftsub[m];
                    root->right = rightsub[n];
                    result.push_back(root);
                   
                }
            }
        }
        return result;
    }
    vector<TreeNode *> generateTrees(int n) {
        if(n==0)
        {
            vector<TreeNode *> result;
            result.push_back(NULL);
            return result;
        }
        return generate(1, n);
    }

Leetcode: Unique Binary Search Trees in C++

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:
int numTrees(int n) {
        vector<int> count(n+1, 0);
        count[0] = 1;
        count[1] = 1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            count[i] += count[j]*count[i-j-1];
        }
        return count[n];
    }

Leetcode: Interleaving String in C++

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbbaccc", return false.

When s3 = "aadbbcbcac", return true.

Solution: 

bool isInterleave(string s1, string s2, string s3) {
        int len1= s1.size();
        int len2 = s2.size();
        int len3 = s3.size();
        if(len1+len2!=len3)
        return false;
        vector<vector<bool> > match(len1+1, vector<bool>(len2+1,false));
        match[0][0] = true;
        for(int i = 0;i<len1;i++)
        {
            if(s1[i]==s3[i])
            match[i+1][0] = true;

            else
            break;

        }
        for(int i = 0;i<len2;i++)
        {
            if(s2[i]==s3[i])
            match[0][i+1] = true;
            else
            break;
        }
        for(int i = 1;i<=len1;i++)
        {
            char c1 = s1[i-1];
            for(int j = 1;j<=len2;j++)
            {
               char c2 = s2[j-1];
               char c3 = s3[i+j-1];
               if(c1==c3) // one situation is related to its previous one and current situation.
               match[i][j] = match[i-1][j]||match[i][j];
               if(c2==c3)
               match[i][j] = match[i][j-1]||match[i][j];
            }
        }
        return match[len1][len2];
    }