LeetCode Q25: Reverse Nodes in k-Group (Hard)

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

1. Recursive solution (my own method)

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverseKGroup(ListNode* head, int k) {
	if(head==NULL||k==1) return head;
	ListNode* p0=head;
	ListNode* p1=head;
	int steps=1;
	while(steps!=k&&p1!=NULL){
	p1=p1->next;
	steps++;
	}
	if(steps!=k||p1==NULL)
	return head;
	ListNode* nextHead=p1->next;
	ListNode* p01=p0->next;
	ListNode* p011;
	while(p0!=p1){
	p011=p01->next;
	p01->next=p0;
	p0=p01;
	p01=p011;
	}
	head->next=reverseKGroup(nextHead, k);
	return p1;
	}
	};

view raw Q25ReverseNodes.cpp hosted with ❤ by GitHub

One thing make me a bit confusing of this solution in the beginning is the use of the reference of the pointer as it is in the parameter list of function reverseKNodes(ListNode* head, int k, ListNode*& start, ListNode*& end). The reason we have to use reference for points here is because, we basically hope reverseKNodes function could change the content which is the address of memory stored in these pointer. However, these pointer is not container of address, they actually the container for ListNode object. So we either should use the pointer of the pointer ListNode ** xxx here or use the reference of the pointer.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverseKGroup(ListNode* head, int k) {
	if(head==NULL||k==1) return head;
	ListNode* p0=head;
	ListNode* p1=head;
	int steps=1;
	while(steps!=k&&p1!=NULL){
	p1=p1->next;
	steps++;
	}
	if(steps!=k||p1==NULL)
	return head;
	ListNode* nextHead=p1->next;
	ListNode* p01=p0->next;
	ListNode* p011;
	while(p0!=p1){
	p011=p01->next;
	p01->next=p0;
	p0=p01;
	p01=p011;
	}
	head->next=reverseKGroup(nextHead, k);
	return p1;
	}
	};

view raw Q25ReverseNodes.cpp hosted with ❤ by GitHub

2. Iterative solution.

This solution is from discuss forum of LeetCode. Author's original post is at: 

https://leetcode.com/discuss/27468/20-line-iterative-c-solution

-1 -> 1 -> 2 -> 3 -> 4 -> 5
 |    |    |    | 
pre  cur  nex  tmp

-1 -> 2 -> 1 -> 3 -> 4 -> 5
 |         |    |    | 
pre       cur  nex  tmp

-1 -> 3 -> 2 -> 1 -> 4 -> 5
 |              |    |    | 
pre            cur  nex  tmp

Above is how it works inside one group iteration(for example, k=3)

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if(head==NULL||k==1) return head;
        int num=0;
        ListNode *preheader = new ListNode(-1);
        preheader->next = head;
        ListNode *cur = preheader, *nex, *tmp, *pre = preheader;
        while(cur = cur->next) 
            num++;
        while(num>=k) {
            cur = pre->next;
            nex = cur->next;
            for(int i=1;inext;
                nex->next = pre->next;
                pre->next = nex;
                cur->next = tmp;
                nex = tmp;
            }
            pre = cur;
            num-=k;
        }
        return preheader->next;
    }
};

Thanks to ciaoliang1992, the tmp pointer is no necessary, so the more concise solution is

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if(head==NULL||k==1) return head;
        int num=0;
        ListNode *preheader = new ListNode(-1);
        preheader->next = head;
        ListNode *cur = preheader, *nex, *pre = preheader;
        while(cur = cur->next) 
            num++;
        while(num>=k) {
            cur = pre->next;
            nex = cur->next;
            for(int i=1;inext=nex->next;
                nex->next=pre->next;
                pre->next=nex;
                nex=cur->next;
            }
            pre = cur;
            num-=k;
        }
        return preheader->next;
    }
};

LeetCode Q24: Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Surprising to see the difficulty level of this question is marked as "Medium". But it could be this hard if you really try to solve it in an iterative way. Because you gonna be very careful doing many swaps in one iteration.

However, your life will get easier if you try a recursive solution which basically just takes you no more than 10 lines code such as the one in the below:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* swapPairs(ListNode* head) {
	if(head==NULL) return head;
	if(head->next==NULL) return head;
	ListNode* p0=head;
	ListNode* p1=head->next;
	ListNode* nextHead=p1->next;
	p1->next=p0;
	p0->next=swapPairs(nextHead);
	return p1;
	}
	};

view raw Q24SwapNodesInPairs.cpp hosted with ❤ by GitHub

Solution 2:

	ListNode* swapPairs(ListNode* head) {
	ListNode* sentinel = new ListNode(0);
	if(head==NULL)
	return sentinel->next;
	sentinel->next = head;
	ListNode* p = sentinel;
	ListNode* p2;
	if(p->next->next!=NULL)
	p2=p->next->next;
	else
	return sentinel->next;
	while(p->next!=NULL&&p2!=NULL){
	ListNode* p1 = p->next;
	p1->next=p2->next;
	p2->next=p1;
	p->next=p2;
	p=p->next->next;
	if(p->next!=NULL&&p->next->next!=NULL)
	p2=p->next->next;
	else
	break;
	}
	return sentinel->next;
	}

view raw Q24-2.cpp hosted with ❤ by GitHub

LeetCode Q23: Merge k Sorted Lists (Hard)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution 1:
The initial idea is very straightforward that every time we take the node with the least number from k lists and link this node to current merged list. To speed up in every round when choosing node with smallest number, I use priority queue.

The code is in following:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	struct compare {
	bool operator()(const ListNode* l, const ListNode* r) {
	return l->val > r->val;
	}
	};
	ListNode* mergeKLists(vector<ListNode*>& lists) {
	ListNode* kLists=NULL;
	ListNode* kListsHead=NULL;
	int k=lists.size();
	int endCount=0;
	priority_queue<ListNode*, std::vector<ListNode*>, compare> heap;
	//fill priority queue
	for(int i=0; i<k; ++i){
	ListNode* p=lists[i];
	if(p!=NULL)
	heap.push(p);
	else
	endCount++;
	}
	while(endCount!=k){
	if(heap.empty())
	return kLists;
	ListNode* node=heap.top();
	heap.pop();
	if(kLists!=NULL){
	kLists->next=node;
	kLists=node;
	}else{
	kLists=node;
	kListsHead=kLists;
	}
	node=node->next;
	if(node==NULL){
	endCount++;
	continue;
	}else
	heap.push(node);
	}
	return kListsHead;
	}
	};

view raw Q23MergekSortedLists.cpp hosted with ❤ by GitHub

Solution 2:
Divide and conque, merge 2 lists at a time. Fastest, 36ms, beat 100%

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* p=NULL;
	if(l1==NULL)
	return l2;
	if(l2==NULL)
	return l1;
	if(l1->val<l2->val){
	p=l1;
	l1=l1->next;
	p->next=mergeTwoLists(l1, l2);
	}else{
	p=l2;
	l2=l2->next;
	p->next=mergeTwoLists(l1, l2);
	}
	return p;
	}
	ListNode* helper(vector<ListNode*>& lists, int s, int e){
	ListNode* res=NULL;
	if(s==e)
	return lists[s];
	if(e-s==1){
	res = mergeTwoLists(lists[s], lists[e]);
	return res;
	}
	int mid = (s+e)/2;
	ListNode* l1 = helper(lists, s, mid);
	ListNode* l2 = helper(lists, mid+1, e);
	res = mergeTwoLists(l1, l2);
	return res;
	}
	ListNode* mergeKLists(vector<ListNode*>& lists) {
	ListNode* res=NULL;
	if(lists.empty())
	return res;
	res = helper(lists, 0, lists.size()-1);
	return res;
	}
	};

view raw Q23-2.cpp hosted with ❤ by GitHub

LeetCode Q22: Generate Parenthesis

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:

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







	class Solution {
	public:
	vector<string> generateParenthesis(int n) {
	vector<string> res;
	addingpar(res, "", n, 0);
	return res;
	}
	void addingpar(vector<string> &v, string str, int n, int m){
	if(n==0 && m==0) {
	v.push_back(str);
	return;
	}
	if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
	if(m > 0){ addingpar(v, str+")", n, m-1); }
	}
	};

view raw Q22GenerateParenthesis hosted with ❤ by GitHub

LeetCode Q21: Merge two sorted lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

The easiest way is to use recursion.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* p=NULL;
	if(l1==NULL)
	return l2;
	if(l2==NULL)
	return l1;
	if(l1->val<l2->val){
	p=l1;
	l1=l1->next;
	p->next=mergeTwoLists(l1, l2);
	}else{
	p=l2;
	l2=l2->next;
	p->next=mergeTwoLists(l1, l2);
	}
	return p;
	}
	};

view raw Q21MergeSortedLists.cpp hosted with ❤ by GitHub

LeetCode Q18: 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)

    (-2,  0, 0, 2)

Extended from 3Sum, fixed the first pointer, and for the last three pointers, solve the problem use 3Sum. 

Solution:
This problem can be downgraded to 3Sum then to 2Sum problem. We will solve the most inner loop using two pointers. For all other loops, we linearly scanning over the given array. The trick here is that in each loop, we skip over identical elements which are not seen the first time.

	class Solution {
	public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
	vector<vector<int> > results;
	if(nums.size()<=3)
	return results;
	sort(nums.begin(), nums.end());
	for(int i0=0; i0<=nums.size()-4; i0++){
	int v0=nums[i0];
	if(i0!=0&&nums[i0]==nums[i0-1])
	continue;
	for(int i1=i0+1; i1<=nums.size()-3; i1++){
	int v1=nums[i1];
	if(i1!=i0+1&&nums[i1]==nums[i1-1])
	continue;
	int i2=i1+1;
	int i3=nums.size()-1;
	while(i2<i3){
	int v2=nums[i2];
	int v3=nums[i3];
	if(i2>i1+1&&nums[i2]==nums[i2-1]){i2++;continue;}
	if(i3<nums.size()-1&&nums[i3]==nums[i3+1]){i3--;continue;}
	int r=v0+v1+v2+v3;
	if(r>target){i3--; continue;}
	if(r<target){i2++; continue;}
	if(r==target){
	vector<int> r={v0, v1, v2, v3};
	i2++;
	i3--;
	results.push_back(r);
	continue;
	}
	}
	}
	}
	return results;
	}
	};

view raw Q184Sum.cpp hosted with ❤ by GitHub

LeetCode Q16: 3Sum Cloest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

I first come up with a wrong solution which seems to be  very reasonable and actually similar to the final correct one. The idea in this wrong solution works by using two pointers pointing to the start and end of the sorted array. In every iteration, search the best result inbetween two pointers. Adjust (increase low point or decrease high pointer) the pointers according to the best result of current iteration. Actually so far I still can not figure out why this solution is wrong. Following is the code for this wrong soluton

• Wrong solution

	#include <stdlib.h>
	#include <stdio.h>
	#include <string>
	#include <vector>
	#include <limits.h>
	using namespace std;
	void sortNums(vector<int>& nums)
	{
	int minv=nums[0];
	int maxv=nums[0];
	for(int i=0; i<nums.size(); ++i)
	{
	if(nums[i]<minv) minv=nums[i];
	if(nums[i]>maxv) maxv=nums[i];
	}
	int len=maxv-minv+1;
	vector<int> bucket(len, 0);
	for(int i=0; i<nums.size(); ++i)
	{
	bucket[nums[i]-minv]++;
	}
	nums.clear();
	for(int i=0; i<bucket.size(); ++i)
	{
	if(bucket[i]==0) continue;
	for(int j=0; j<bucket[i]; ++j)
	{
	nums.push_back(minv+i);
	}
	}
	}
	int threeSumClosest(vector<int>& nums, int target)
	{
	sortNums(nums);
	for(int i=0; i<nums.size(); ++i){
	printf("%d\n", nums[i]);
	}
	int s=0;
	int e=nums.size()-1;
	int cloest=INT_MAX;
	int result=0;
	while(s<=e-2)
	{
	int v0=nums[s];
	int v2=nums[e];
	for(int i=s+1; i<e; i++)
	{
	int v1=nums[i];
	int tmpr=v0+v1+v2;
	if(abs(tmpr-target)<cloest)
	{
	cloest=abs(tmpr-target);
	result=tmpr;
	}
	}
	if(result<target)
	s++;
	if(result>target)
	e--;
	if(result==target)
	return result;
	}
	return result;
	}
	int main(int argc, char** argv)
	{
	int a[]= {4,0,5,-5,3,3,0,-4,-5};
	int target = -2;
	vector<int> nums(a, a+sizeof(a)/sizeof(int));
	int r=threeSumClosest(nums, target);
	int zx=0;
	}

view raw Q16Wrongsolution.cpp hosted with ❤ by GitHub

In correct solution, the idea is very similar to the one I described above. But difference is that, in this solution, in i=th iteration we keep the first pointer fixed at i-th element, and start a same searching process using two pointers as I described in the wrong solution. Following is the code for this correct solution 

• Correct solution

	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))
	res = sum;
	if(sum<target)
	p0++;
	else
	p1--;
	}
	}
	return res;
	}
	};

view raw Q16CorrectSolution.cpp hosted with ❤ by GitHub

How to create virtual environment for Python

Please refer to this fantastic post.

LeetCode Q15: 3 Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

My solution:
O(n^2).

	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])
	continue;
	int sum = 0-nums[i];
	int p0=i+1, p1=nums.size()-1;
	while(p0<p1){
	if(p0>i+1&&nums[p0]==nums[p0-1]){
	p0++;
	continue;
	}
	if(p1<nums.size()-1&&nums[p1]==nums[p1+1]){
	p1--;
	continue;
	}
	int tmp = nums[p0]+nums[p1];
	if(tmp==sum){
	vector<int> v={nums[i], nums[p0], nums[p1]};
	res.push_back(v);
	p0++; p1--;
	}else{
	if(tmp<sum)
	p0++;
	else
	p1--;
	}
	}
	}
	return res;
	}
	};

view raw Q153sum.cpp hosted with ❤ by GitHub

LeetCode Q11: Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

• Mehtod1

Most naive way, two loops .

• Method2

	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);
	int r1=dp[s][e-1]!=-1? dp[s][e-1] : helper(height, s, e-1, dp);
	int r2=min(height[s], height[e])*(e-s);
	dp[s][e]=max(r0, max(r1, r2));
	return dp[s][e];
	}
	int maxArea(vector<int>& height) {
	vector<vector<int> > dp(height.size(), vector<int>(height.size(), -1));
	return helper(height, 0, height.size()-1, dp);
	}
	};

view raw q11ContainerMostWater2 hosted with ❤ by GitHub

• Method3

O(n) time method, use two pointers to scan the array once.
Suppose two points are s, e. In the beginning, s at the left end, e at the right end. The goal is to maximize the area. So, in this case, we always try to move the shortest bar between s and e to left(s) or to right(e) to look for next bigger area.

	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)
	{
	if(height[s]<=height[e]){
	s++;
	}
	else{
	e--;
	}
	int tmp=min(height[s], height[e])*(e-s);
	if(tmp>maxarea){
	maxarea=tmp;
	}
	}
	return maxarea;
	}
	};

view raw Q11ContainerMostWater hosted with ❤ by GitHub

LeetCode Q4: Median of Two Sorted Arrays (Hard)

Let's consider a more general solution, specifically, a method similar to finding the k-th smallest element in an array and remove elements smaller than k in each iteration.

Assume that the number of elements in A and B are both larger than k/2, and if we compare the k/2-th smallest element in A(i.e. A[k/2-1]) and the k-th smallest element in B(i.e. B[k/2 - 1]), there are three results:
(Becasue k can be odd or even number, so we assume k is even number here for simplicy. The following is also true when k is an odd number.)
A[k/2-1] = B[k/2-1]
A[k/2-1] > B[k/2-1]
A[k/2-1] < B[k/2-1]
if A[k/2-1] < B[k/2-1], that means all the elements from A[0] to A[k/2-1](i.e. the k/2 smallest elements in A) are in the range of k smallest elements in the union of A and B. Or, in the other word, A[k/2 - 1] can never be larger than the k-th smalleset element in the union of A and B.

Why?
We can use a proof by contradiction. Since A[k/2 - 1] is larger than the k-th smallest element in the union of A and B, then we assume it is the (k+1)-th smallest one. Since it is smaller than B[k/2 - 1], then B[k/2 - 1] should be at least the (k+2)-th smallest one. So there are at most (k/2-1) elements smaller than A[k/2-1] in A, and at most (k/2 - 1) elements smaller than A[k/2-1] in B.So the total number is k/2+k/2-2, which, no matter when k is odd or even, is surly smaller than k(since A[k/2-1] is the (k+1)-th smallest element). So A[k/2-1] can never larger than the k-th smallest element in the union of A and B if A[k/2-1]Since there is such an important conclusion, we can safely drop the first k/2 element in A, which are definitaly smaller than k-th element in the union of A and B. This is also true for the A[k/2-1] > B[k/2-1] condition, which we should drop the elements in B.
When A[k/2-1] = B[k/2-1], then we have found the k-th smallest element, that is the equal element, we can call it m. There are each (k/2-1) numbers smaller than m in A and B, so m must be the k-th smallest number. So we can call a function recursively, when A[k/2-1] < B[k/2-1], we drop the elements in A, else we drop the elements in B.


We should also consider the edge case, that is, when should we stop?
1. When A or B is empty, we return B[k-1]( or A[k-1]), respectively;
2. When k is 1(when A and B are both not empty), we return the smaller one of A[0] and B[0]
3. When A[k/2-1] = B[k/2-1], we should return one of them

In the code, we check if m is larger than n to garentee that the we always know the smaller array, for coding simplicy.

	//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]);
	int a = min((k+1)/2, n1), b = k+1-a;
	if(nums1[s1+a-1]<=nums2[s2+b-1]){
	return findKth(nums1, nums2, k-a, s1+a, s2);
	}else{
	return findKth(nums1, nums2, k-b, s1, s2+b);
	}
	}
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	int n1 = nums1.size(), n2 = nums2.size(), n = n1+n2;
	if(n%2==1){
	return findKth(nums1, nums2, n/2, 0, 0);
	}else{
	return (findKth(nums1, nums2, n/2-1, 0, 0)+findKth(nums1, nums2, n/2, 0, 0))/2.0;
	}
	}
	};

view raw Q4MedianTwoSortedArrays.cpp hosted with ❤ by GitHub

LeetCode Q10: Regular Expression Matching

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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

Solution:

This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:

1. f[i][j] = f[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. f[i][j] = f[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. f[i][j] = f[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

Putting these together, we will have the following code.

	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;
	int tmp=f[sS][pS];
	return f[sS][pS];
	}
	if(p[pS+1]!='*')
	{
	if(sS<sSize && (p[pS]==s[sS] || p[pS]=='.'))
	if(f[sS+1][pS+1]!=-1)
	{
	f[sS][pS]=f[sS+1][pS+1];
	int tmp=f[sS][pS];
	return f[sS][pS];
	}
	else
	{
	f[sS][pS]=helper(s, p, sS+1, pS+1, f);
	int tmp=f[sS][pS];
	return f[sS][pS];
	}
	}
	else
	{
	if(f[sS][pS+2]==-1)
	{
	f[sS][pS]=helper(s, p, sS, pS+2, f);
	int tmp=f[sS][pS];
	if(f[sS][pS]==1)
	return true;
	}
	while(sS<sSize && (p[pS]==s[sS] || p[pS] == '.'))
	{
	if(f[sS+1][pS+2]==-1)
	{
	f[sS][pS]=helper(s, p, sS+1, pS+2, f);
	int tmp=f[sS][pS];
	if(f[sS][pS]==1)
	return true;
	}
	sS++;
	}
	}
	f[sS][pS]=0;
	return false;
	}
	bool isMatch(string s, string p)
	{
	vector<vector<int> > f(s.length()+1, vector<int>(p.length()+1, -1));
	return helper(s, p, 0, 0, f);
	}
	};

view raw Q10DP.cpp hosted with ❤ by GitHub

	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]
	* 2) "x*" repeats >= 1 times and matches "x*x": s[i - 1] == x && f[i - 1][j]
	* '.' matches any single character
	*/
	int m = s.size(), n = p.size();
	vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
	f[0][0] = true;
	for (int i = 1; i <= m; i++)
	f[i][0] = false;
	// p[0.., j - 3, j - 2, j - 1] matches empty iff p[j - 1] is '*' and p[0..j - 3] matches empty
	for (int j = 1; j <= n; j++)
	f[0][j] = j > 1 && '*' == p[j - 1] && f[0][j - 2];
	for (int i = 1; i <= m; i++)
	for (int j = 1; j <= n; j++)
	if (p[j - 1] != '*')
	f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || '.' == p[j - 1]);
	else
	// p[0] cannot be '*' so no need to check "j > 1" here
	f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];
	return f[m][n];
	}
	};

view raw q10recursion.cpp hosted with ❤ by GitHub

How to insert code to Blogger

I basically following this blog

 Yet, the easiest way is to use Github GIST https://gist.github.com/, I love it to died!

Hello Blogger!

Hello Blogger!