[Leetcode] Interleaving String

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 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

k chars s3 could be an interleaving string of  i s1 chars and j s2 chars if i + j = k;  if we know the s3 is an interleaving string of s1 and s2, then if  s3[k+1] == s1[i+1] or s3[k+1] == s2[j+1],  s3 is also an interleaving string of s1 and s2 by simply appending s1[i+1] or s2[j+1] to s3. Based on the observation,  let f[i][j] be true if s3 is the interleaving string of first i chars of s1 and first  j chars of s2; and false otherwise, we can have the transition function:

f[i][j] = f[i-1][j] && s1.substr(i-1, 1) == s3.substr(i+j-1, 1) || f[i][j-1] & s2.substr(j-1, 1) == s3.substr(i+j-1, 1))
f[i][j]  = true, if I =0, j =0

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size())
            return false;
        vector<vector<bool> > f(s1.size()+1, vector<bool>(s2.size()+1, false));
        for(int i=0; i<=s1.size(); i++)
        {
            for(int j=0; j<=s2.size(); j++)
            {
                if (i == 0 && j == 0)
                    f[i][j] = true;
                else if (i == 0)
                    f[i][j] = f[i][j-1] && (s2[j-1] == s3[j-1]);
                else if (j == 0)
                    f[i][j] = f[i-1][j] && (s1[i-1] == s3[i-1]);
                else
                    f[i][j] = (f[i][j-1] && (s2[j-1] == s3[i+j-1])) || (f[i-1][j] && (s1[i-1] == s3[i+j-1])) ;
            }
        }
        
        return f[s1.size()][s2.size()];
    }
};

//Solution 2: Recursive
bool isInterleaveHelper(string s1, int i, string s2, int j, string s3,int k) {
    if (k == s3.size())
        return true;
    else
    {
        if (s1[i] == s3[k] && s2[j] == s3[k])
            return isInterleaveHelper(s1, i+1, s2, j, s3, k+1) || isInterleaveHelper(s1, i, s2, j+1, s3, k+1);
        else if (s1[i] == s3[k])
            return isInterleaveHelper(s1, i+1, s2, j, s3, k+1);
        else if (s2[j] == s3[k])
            return isInterleaveHelper(s1, i, s2, j+1, s3, k+1);
        else
            return false;
    }
}

bool isInterleave(string s1, string s2, string s3) { 
    if (s1.size() + s2.size() != s3.size())
        return false;
    return isInterleaveHelper(s1, 0, s2, 0, s3, 0);
}

[Leetcode] Longest Valid Parentheses

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.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

Using a stack to push and pop the valid parentheses and the left in the stack is the invalid parentheses. These invalid parentheses are the separator of all groups of valid parentheses.  If we know the index of the invalid parenthesis, then the gap  between indexes are the length of the valid parentheses.

Example: ()(()()()

Invalid parentheses index : 2. So the valid parentheses are 0 to 2 and 2 to 9, which is 6.

int longestValidParentheses(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int n = s.size();
    int maxLength = 0;
    stack idxStack;
    for (int i=0; i 0)
                idxStack.pop();
            else
                idxStack.push(-1*(i+1)); //use negative to indicate it is  ")"
        }
    }
   
    int e = n + 1;  //the last invalid index is n+1
    while(!idxStack.empty())
    {
        int idx = abs(idxStack.top());
        maxLength = max(maxLength, e - idx -1);
        e = idx;
        idxStack.pop();
    }
   
    maxLength = max(maxLength, e - 1); //the first invalid index is 0 (index in stack begin from 1)

    return maxLength;

}

[Leetcode] Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:

S = "rabbbit", T = "rabbit"

Return 3.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

If S[0] = T[0], then T is a subsequence of S if

• the rest of string T is a subsequence the rest of string S,  or

• T is a subsequence of the rest of string S

If S[0] != T[0], then T cannot be a subsequence of S; it could only be the subsequence  of the rest of S.

Let S'[i] be the suffix of S beginning from index i, and T'[j] be the suffix of T beginning from index j and f[i][j] is the number of subsequence of S'[i] and T'[j]. By the above analysis, we can get the transition function of DP as

• f[i][j] = f[i+1][j+1] + f[i+1][j], if S[i] == T[j]
• f[i][j] = f[i+1][j], if S[i] != T[j]

Now consider the end condition: if j reached the end of string T, that means, all chars in T has been satisfied in S  (from the transition function we  can notice that the j increased only when S[i] == T[j]), the subsequence has already been found in S. On the other hand, if the end of string S was reached, and end of string T was not, no subsequence was found.

• f[i][j] =1, if j == T.size()
• f[i][j] = 0, if I ==S.size() &&  j != T.size()

int numDistinct(string S, string T) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int m = S.size();
    int n = T.size();
    if (m == 0 || n == 0)
        return 0;

    vector v(n + 1,0);
    vector > f(m + 1, v);

    for (int i=m; i>=0; i--)
    {
        for (int j=n; j>=0; j--)
        {
            if (j == n)
                f[i][j] = 1;
            else if (i == m)
                f[i][j] = 0;
            else if (S[i] != T[j])
                f[i][j] = f[i+1][j];
            else
                f[i][j] = f[i+1][j+1] + f[i+1][j];
        }
    }
    return f[0][0];
}

[Leetcode] Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Pasted from <http://leetcode.com/onlinejudge>

Analysis: 


Find the max height at i, then the trapped water at position j less than (at left of) i depends on its max height on the left of i; similarly, the trapped water at position j greater than (at the right of) i depends on its max height on the right of j. No extra space needed for the solution.

int trap(int A[], int n) {
    int maxHeight = 0;
    int maxHeightPos = 0;
    for (int i=0; i maxHeight) {
            maxHeight = A[i];
            maxHeightPos = i;
        }
    }

    int sum = 0;
    int leftHeight = 0;
    for (int i=0; i < maxHeightPos; i++)
    {
        sum += max (0, leftHeight - A[i]);
        leftHeight = max (A[i], leftHeight);
    }

    int rightHeight = 0;
    for (int i=n-1; i > maxHeightPos; i--)
    {
        sum += max (0, rightHeight - A[i]);
        rightHeight = max (A[i], rightHeight);
    }

    return sum;
}

[Leetcode] Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

[1,1,2] have the following unique permutations:

[1,1,2], [1,2,1], and [2,1,1].

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

Given [1,1,2], by normal permutations, we will have the following sequence:

1, 1, 2,

1, 2, 1,

1, 1, 2

1, 2, 1

2, 1, 1

2, 1, 1

We noticed that there is duplicate because the black "1" did the same routine as the red "1". So, if let the black "1" be able to be used only when the red "1" is being used, we can rule out the duplicate permutation. 

void permuteUniqueHelper(vector >& permutations, vector permutation, const vector &num, vector used) {
    if (permuations.size() == num.size())
        permutations.push_back(permutation);
    else
    {
        for (int i=0; i < num.size(); i++)
        {
            if (used[i] || (i > 0 && num[i] == num[i-1] && !used[i-1]))
                continue;
            used[i] = true;
            permutation.push_back(num[i]);
            permuteUniqueHelper(permutations, permutation, num, used);
            used[i] = false;
            permutation.pop_back();
        }  
    }      
}

vector > permuteUnique(vector &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector > permutations;
    vector permutation;
    vector used(num.size(), false);
    permuteUniqueHelper(permutations, permutation, num, used);
   
    return permutations;

}

[Leetcode] Reverse Nodes in k-Group

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

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

1-->2-->3-->4-->5-->NULL

^p1       ^p2

NewNode->NULL

^p

After first iteration

1-->2-->3-->4-->5-->NULL

           ^p1          ^p2

NewNode-->2->1-->NULL

                            ^p

Use p2 to probe whether we still need to reverse the group.  If there is still more than k nodes left, iterate all node between p1 and p2 and insert it after p. Move p so that it always points to end of the new list.

ListNode *reverseKGroup(ListNode *head, int k) {
    ListNode* newNode = new ListNode(0);
    ListNode* p2 = head;
    ListNode* p1 = head;
    ListNode* p = newNode;
    while(1)
    {
        int i = 0;
        while(p2 != NULL && i < k)
        {
            i++;
            p2 = p2->next;
        }

        if (i != k)
            break;

        while(p1 != p2)
        {
            //insert p1 after p
            ListNode* next = p1->next;
            p1->next = p->next;
            p->next = p1;
            p1 = next;
        }

        //move p to end of the new list
        while(p != NULL &&p->next != NULL)
            p = p->next;
    }
    if (p != NULL)
        p->next = p1;
    head = newNode->next;
    delete newNode;
    return head;
} 

[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.

From <http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/>

Analysis: Every time the node reach a leaf, add the sum to the total; Otherwise, continue accumulating the sum value.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void helper(TreeNode *root, int num, int& sum) {
        if (root == NULL)
            return;
        else 
        {
            num = num * 10 + root->val;
            if (root->left == NULL && root->right == NULL)
                sum += num;
            helper(root->left, num, sum);
            helper(root->right, num, sum);
        }
        
    }

    int sumNumbers(TreeNode *root) {
        int sum = 0;
        helper(root, 0, sum);
        return sum;
    }
};

[Leetcode] Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Analysis:

We notice that a node is distinct if the node value is not equal to both its previous node value and next node value. So simply taking these node out would be the solution. Note you need to take care of the NULL previous and next node. Use a temporary new head to decrease the code complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {

        ListNode* newHead = new ListNode(0);
        ListNode* p = newHead;
        ListNode* prev = NULL;
        while(head != NULL)
        {
            if ((prev == NULL || (prev != NULL && head->val != prev->val)) &&
                (head->next == NULL || (head->next != NULL && head->val != head->next->val)))
            {
                p->next = head;
                p = p->next;
            }
            prev = head;
            head = head->next;
        }
        p->next = NULL;
        head = newHead->next;
        delete newHead;
        return head;
    }
};

//solution 2:
ListNode *deleteDuplicates(ListNode *head) {
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* curr = head;
    ListNode* prev = dummyHead;
    while(curr != NULL && curr->next != NULL)
    {
        if (curr->val == curr->next->val)
        {
            while(curr->next != NULL && curr->val == curr->next->val)
            {
                ListNode* tmp = curr->next;
                prev->next = curr->next;
                delete curr;
                curr = tmp;
            }
            //remove the last element
            ListNode* tmp = curr->next;
            prev->next = curr->next;
            delete curr;
            curr = tmp;  
            
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }
    
    return dummyHead->next;
}

[Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

If we can use O(n) space , it is straight forward to get the  solution: do an in-order travel and put the node in the array; iterate the array and you will find the two which are not in ascending order.

But do we really need O(n) space?  Basically, if we can get the node p1 and p2, then swapping the value of p1 and p2 would recover the tree.  We don't have to remember all other nodes.  So when we do an in-order travel and compare the current node value with the previous node value, if we can find a node which has a value less than the previously visited node, either the current node or the previous node are the node swapped by mistake. There are two scenario to be considered: the node swapped are neighbors or not neighbors.

1,  2,  5,  4,  3,  6

         ^p1     ^p2

1,  2,  4,  3,  5,  6

          ^p1^p2

The code simply express themselves. 

Note, iterative in-order travel does not work for this questions since it use O(n) space for the stack.  

void recoverTreeHelper(TreeNode *root, TreeNode*& prev, TreeNode* &p1, TreeNode* &p2) {

    if (root != NULL)
    {
        recoverTreeHelper(root->left, prev, p1, p2);
        if (prev != NULL && root->val < prev->val)
        {
            if (p1 == NULL) {
                p1 = prev;
                p2 = root;
            }
            else
                p2 = root;
        }
        else
            prev = root;

        recoverTreeHelper(root->right, prev, p1, p2);
    }
}

void recoverTree(TreeNode *root) {

    TreeNode* p1 = NULL;
    TreeNode* p2 = NULL;
    TreeNode* prev = NULL;

    recoverTreeHelper(root, prev, p1, p2);

    if (p1 != NULL && p2 != NULL)
        swap(p1->val, p2->val);
} 

[Leetcode] ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Pasted from <http://leetcode.com/onlinejudge#question_1>

Analysis:

1P		9H
2A	8S	10I	16
3Y	7I	11N	15
4P	6L	12G	14
5A		13

j = nRows*2 -2 if i = 0 || nRows-1, 

j = (nRows-i)*2  if i>0 && i<nRows-1, c is odd

j = i*2 c is even

class Solution {
public:
    string convert(string s, int nRows) {
        
        if(nRows <= 1) return s;
        
        string str;
        for(int i=0; i < nRows; i++)
        {
            int j = i;    
            int c = 0;
            while( j < s.size())
            {
                str.push_back(s[j]);
                c++;
                if (i == 0 || i == nRows - 1)
                    j = j + nRows + nRows - 2;
                else 
                {
                    if (c % 2 == 1)
                        j = j + (nRows-i - 1) * 2;
                    else
                        j = j + i * 2;
                }
            }
        }
        
        return str;
    }
};

[Leetcode] Reverse digits of an integer

Reverse digits of an integer.

Example1: x = 123, return 321

Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Pasted from <http://discuss.leetcode.com/questions/191/reverse-integer>

class Solution {
public:
    int reverse(int x) {
        bool neg = x < 0 ? true : false;
        long long absx = abs((long long)x);
        long long ret = 0;
        while(absx)
        {
            ret = ret * 10 + absx % 10;
            absx = absx / 10;
            if (ret > INT_MAX)
                return neg?INT_MIN:INT_MAX;
        }
        
        return neg? 0- ret : ret;
    }
};

[Leetcode] Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Pasted from <http://leetcode.com/onlinejudge>

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        long long absx = abs((long long)x);
        int k=1;
        int x1 = absx;
        while(x1  >= 10)
        {
            x1 = x1 / 10;
            k = k * 10;
        }
        
        x1 = absx;
        while(x1)
        {
            if (x1 / k != x1 %10)
                return false;
            x1 = (x1 % k) / 10;
            k = k / 100;
        }
        
        return true;
    }
};

[Leetcode] 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.

Pasted from <http://leetcode.com/onlinejudge>

//Solution1:  brute force
int maxArea(vector &height) {
    int maxVal = 0;
    for (int i=0; i maxVal)
                maxVal = area;
        }
    }
   
    return maxVal;
}

	
//Solution2:  two pointers
int maxArea(vector &height) {
    int i = 0;
    int j = height.size() - 1;
    int maxAreas = min(height[j],height[i])*(j-i);
    while (i < j)
    {
        if (height[i] >= height[j])
            j--;
        else
            i++;
        int area = (j-i) * min(height[i],height[j]);
        if (area > maxAreas)
            maxAreas = area;
    }
    return maxAreas;
}

[Leetcode] Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis:

IV, IX, XL, XC, XD, CM could be summarized as m[s[i+1]]-m[s[i]].

int romanToInt(string s) {
    map m;
    m['I'] = 1;
    m['V'] = 5;
    m['X'] = 10;
    m['L'] = 50;
    m['C'] = 100;
    m['D'] = 500;
    m['M'] = 1000;
    
    int i=0; 
    int ret = 0;
    while(i < s.size())
    {
        if ((s[i] == 'I' && i + 1 < s.size() && (s[i+1] == 'V' || s[i+1] == 'X')) ||
            (s[i] == 'X' && i + 1 < s.size() && (s[i+1] == 'L' || s[i+1] == 'C')) ||
            (s[i] == 'C' && i + 1 < s.size() && (s[i+1] == 'D' || s[i+1] == 'M')))
        {
            ret = ret + (m[s[i+1]] - m[s[i]]);
            i = i+2;
        }
        else
        {
            ret = ret + m[s[i]];
            i = i + 1;
        }    
    }
    return ret;
}

[Leetcode] Integer to Roman

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

void generateString(char one, char five, char ten,vector& strs)
{
    int i = 1;
    while(i <= 9)
    {
        string str;
        if (i >= 1 && i<= 3)
        {
            str.append(i, one);
        }
        else if (i == 4)
        {
            str.append(1, one);
            str.append(1, five);
        }                
        else if (i == 5)
        {
            str.append(1, five);
        }
        else if (i >= 6 && i <=8)
        {
            str.append(1, five);
            str.append(i-5, one);
        }
        else if (i == 9)
        {
            str.append(1, one);
            str.append(1, ten);
        }
        strs.push_back(str);
        i++;
    }
}

string intToRoman(int num) {
    
    vector n1;
    generateString('I','V','X', n1);

    vector n10;
    generateString('X','L','C', n10);
    
    vector n100;
    generateString('C','D','M', n100);
    
    string ret;
    int d1 = num / 1000;
    if ( d1 > 0)
        ret.append(d1, 'M');
   
    int d2 = (num % 1000)/100;
    if ( d2 > 0)
        ret.append(n100[d2-1]);
        
    int d3 = (num % 100)/10;
    if ( d3 > 0)
        ret.append(n10[d3-1]);
        
    int d4 = num % 10;
    if ( d4 > 0)
        ret.append(n1[d4-1]);
        
    return ret;
}

[Leetcode] Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

Pasted from <http://leetcode.com/onlinejudge>

In the example, get p => 4, head =>1, 5 => last, 3=>prev

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (head == NULL || head->next == NULL)
            return head;
            
        int l = 0;
        ListNode* curr = head;
        ListNode* last = head;
        while(curr != NULL)
        {
            last = curr;
            curr = curr->next;
            l++;
        }
		
        int i = 1;
        ListNode* p = head;
        while(p != NULL && i < l - k % l)
        {
            i++;
            p = p->next;
        }
        
        last->next = head;
        ListNode* newHead = p->next;
         p->next  = NULL;
        
        return newHead;
    }
};

[Leetcode] Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:

You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
    
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        while(j >= 0)
        {
            if (i < 0)
                A[k--] = B[j--];
            else if (A[i] >= B[j])
                A[k--] = A[i--];
            else
                A[k--] = B[j--];
        }
    }
};