xzhang311

class Solution { private: bool helper(const string &s, const string &p, int sS, int pS) { int sSize = s.size(), pSize = p.size(), i, j; if(pS==pSize) return sS ==sSize; // if p goes to its end, then only if s also goes to its end to return true;

    if(p[pS+1]!='*'){
       if( sS<sSize && (p[pS]==s[sS] || p[pS] == '.')) return helper(s, p, sS+1, pS+1);

}

xzhang311

class Solution {
public:
    bool isMatch(string s, string p) {
        /**
         * f[i][j]: if s[0..i-1] matches p[0..j-1]
         * if p[j - 1] != '*'
         *      f[i][j] = f[i - 1][j - 1] && s[i - 1] == p[j - 1]
         * if p[j - 1] == '*', denote p[j - 2] with x
         *      f[i][j] is true iff any of the following is true
         *      1) "x*" repeats 0 time and matches empty: f[i][j - 2]

xzhang311

class Solution {
public:
bool helper(const string &s, const string &p, int sS, int pS, vector<vector<int> >& f)
{
    int sSize=s.length();
    int pSize=p.length();

    if(pS==pSize)
    {
        f[sS][pS]=(sS==sSize)? 1:0;

xzhang311

class Solution {
public:
    int findK(int A[], int m, int B[], int n, int k){
        if(m>n) return findK(B, n, A, m, k);
        if(m==0) return B[k-1];
        if(k==1) return min(A[0], B[0]);
        int a=min(k/2, m);
        int b=k-a;
        if(A[a-1]<=B[b-1]){
            return findK(A+a, m-a, B, n, k-a);

xzhang311

//C: 40ms
class Solution {
public:
    int findKth(vector<int>& nums1, vector<int>& nums2, int k, int s1, int s2){
        int n1 = nums1.size()-1-s1+1, n2 = nums2.size()-1-s2+1, n = n1+n2;
        if(n1>n2) return findKth(nums2, nums1, k, s2, s1);
 
        if(n1<=0) return nums2[s2+k];
        if(k==0) return min(nums1[s1], nums2[s2]);
 

xzhang311

class Solution {
public:
int maxArea(vector<int>& height)
{
    int s=0;
    int e=height.size()-1;
    int maxarea=min(height[s], height[e]) * (e-s);

    while(s!=e)
    {

xzhang311

recursive dp version
class Solution {
public:
    int helper(vector<int>& height, int s, int e, vector<vector<int> >& dp) {
        if(s==e){
            dp[s][e]=0;
            return 0;
        }
            
        int r0=dp[s+1][e]!=-1? dp[s+1][e] : helper(height, s+1, e, dp);

xzhang311

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > res;
        if(nums.size()==0||nums.size()<3)
            return res;
        sort(nums.begin(), nums.end());
        
        for(int i=0; i<nums.size()-2; i++){
            if(i>=1&&nums[i]==nums[i-1])

xzhang311

#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <vector>
#include <limits.h>

using namespace std;

void sortNums(vector<int>& nums)
{

xzhang311

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        long res=INT_MAX;
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size()-2; i++){
            int p0 = i+1, p1 = nums.size()-1;
            while(p0<p1){
                int sum = nums[i]+nums[p0]+nums[p1];
                if(abs(sum-target)<abs(res-target))