9 Palindrome Number

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

Solution 1: Use String
class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0)
            return false;
        if (x==0)
            return true;
        string original = to_string(x);
        string reverse;
        while(x>0)
        {
            reverse.push_back(x%10 + '0');
            x /= 10;
        }
        return reverse == original;
    }
};

Solution 2: Use integer
class Solution {
public:
    bool isPalindrome(int x) {
        if (x==0)
            return true;
        if (x<0|| x%10==0)
            return false;
        
        int y = 0;
        while(x>y)
        {
            y = y*10 + x%10;
            if (x==y)
                return true;
            x /= 10;
        }
        return x==y;
    }
};

2 Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (!l1)
            return l2;
        if (!l2)
            return l1;
        ListNode *dummy = new ListNode(0);
        ListNode *tmp = dummy;
        int carry = 0;
        while(l1 || l2 || carry>0)
        {
            int num1 = l1? l1->val:0;
            int num2 = l2? l2->val:0;
            int sum = (num1+num2+carry)%10;
            carry = (num1+num2+carry)/10;
            tmp->next = new ListNode(sum);
            tmp = tmp->next;
            l1 = l1? l1->next:l1;
            l2 = l2? l2->next:l2;
        }
        tmp = dummy->next;
        delete dummy;
        return tmp;
        
    }
};

69 Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

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

159 Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char,int> mp;
        int start=0;
        int end = 0;
        int max_len=0;
        int count=0;
        while(end<s.size())
        {
            if (count<2)
            {
                if (mp.find(s[end])==mp.end() || mp[s[end]]<start)
                {
                    count++;
                }
                mp[s[end]]=end;
            }
            else
            {
                if (mp.find(s[end])==mp.end()|| mp[s[end]]<start)
                {
                    count++;
                    while(count>2)
                    {
                        if (mp[s[start]]<=start)
                        {
                            mp.erase(s[start]);
                            count--;
                        }
                        start++;
                    }
                }
                mp[s[end]]=end;
            }
            end++;
            if (count<=2)
            {
                max_len = max(max_len,end-start);
            }
        }
        return max_len;
    }
};

157 Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
        int res = 0;
        int read_char = 0;
        while (res<n)
        {
            read_char = read4(buf+res);
            res += read_char;
            if (read_char<4)
                break;
        }
        if (res>=n)
        {
            buf[n]='\0';
            res = n;
        }
        return res;
    }
};

163 Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

class Solution {
public:
    vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
        vector<string> res;
        for (int i=0;i<n;i++)
        {
            if (A[i]>upper)
                break;
            else if (A[i]==upper)
                upper--;
            else if (A[i]<lower)
                continue;
            else if (A[i]==lower)
                lower++;
            else
            {
                if (A[i]-lower==1)
                {
                    res.push_back(to_string(lower));
                    lower = A[i]+1;
                }
                else
                {
                    string range = to_string(lower)+"->"+to_string(A[i]-1);
                    res.push_back(range);
                    lower = A[i]+1;
                }
            }
        }
        if (lower<upper)
            res.push_back(to_string(lower)+"->"+to_string(upper));
        else if (lower == upper)
            res.push_back(to_string(lower));
        return res;
    }
};

31 Next Permutation

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,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.size()<=1)
            return;
        int i=num.size()-1;
        while(i>0 && num[i]<=num[i-1])
            i--;
        if (i==0)
        {
            sort(num.begin(),num.end());
            return;
        }
        i--;
        int j=num.size()-1;
        while(j>i && num[j]<=num[i])
            j--;
        swap(num[i],num[j]);
        sort(num.begin()+i+1,num.end());
    }
};

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

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * 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 recoverTree(TreeNode *root) {
        TreeNode *pre = NULL;
        TreeNode *first = NULL;
        TreeNode *second = NULL;
        inorderTraversal(root,pre,first,second);
        int tmp = first->val;
        first->val = second->val;
        second->val = tmp;
    }
    void inorderTraversal(TreeNode *root, TreeNode* & pre, TreeNode *&first, TreeNode* &second)
    {
        if (!root)
            return;
        inorderTraversal(root->left,pre,first,second);
        if (pre && pre->val>root->val)
        {
            if (!first)
                first = pre;
            second = root;
        }
        pre = root;
        inorderTraversal(root->right,pre,first,second);
    }
};

Leetcode 187 Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution: 
基本思路，每十个字符当成一个string扫描。map里面没有就存入map,map里有且之前没有存入result中就存入，如果已经存过就跳过。
难点：string存入map太占地方，每个字符一个byte，每个string要10个byte。解决方法用bit map：ACGT一共4种二进制编码：A:00,C:01,G:10,T:11,每个字符只需要2bit，每个string 20bit=3bytes就够了。

1.每十个字符当成一个string扫描，对每个字符转换成int。
转换方法：按字符扫描，原结果左移2位，然后最低两位按编码设定即可。
如：GTCA：
第一次扫描A： result=10b
第二次扫描T: result先左移2位：result=1000b，再设置最低2位为11：result=1011b
第三次赛秒C：result先左移2位(<<2)，再最低2位设置为二进制01 (和01b与)： result = result<<2 |01
注意：上面都是二进制数，但是c++没有直接二进制数的表达方法，所以要转换成10进制数进行与运算。

2. 如果map里面没有，就存入map，设置个数为1。
如果map里面已有，且个数为1，表示之前有且仅有一个，则记录在result里，改变个数为-1；如果map里面有，但是个数不为1，代表已经记录在result了，不操作。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size()<10)
            return res;
        unordered_map<int,int> mp;
        for (int i=0;i<(int)s.size()-9;i++)
        {
            string tmp_str = s.substr(i,10);
            int str_val = strToInt(tmp_str);
            if (mp.find(str_val)==mp.end())
            {
                mp[str_val]=1;
            }
            else
            {
                if (mp[str_val]==1)
                {
                    mp[str_val]=-1;
                    res.push_back(tmp_str);
                }
            }
        }
        return res;
    }
    int strToInt(string s)
    {
        int res=0;
        for (int i=0;i<s.size();i++)
        {
            if (s[i]=='A')
                res = res<<2;
            else if (s[i]=='C')
                res = res<<2|1;
            else if (s[i]=='G')
                res = res<<2 |2;//binary 10 = 2
            else
                res = res <<2 |3;//binary 11 = 3
        }
        return res;
    }
};

179 Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

class Solution {
public:
    string largestNumber(vector<int> &num) {
        vector<string> str;
        for (int i=0;i<num.size();i++)
            str.push_back(to_string(num[i]));
        sort(str.begin(),str.end(),compare);
        string res;
        int i=0;
        while(i<str.size()-1 && str[i]=="0")
            i++;
        for (;i<str.size();i++)
            res += str[i];
        return res;
    }
    static bool compare(string s1,string s2)
    {
        return (s1+s2)>(s2+s1);
    }
};

148 Sort List

Sort a linked list in O(n log n) time using constant space complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next)
            return head;
        int len=0;
        ListNode *tmp = head;
        while(tmp)
        {
            tmp=tmp->next;
            len++;
        }
        return mergeSort(head,len);
    }
    ListNode* mergeSort(ListNode *head,int n)
    {
        if (n<=1)
            return head;
        int len=n/2;
        ListNode *tmp = head;
        while(len>1)
        {
            tmp = tmp->next;
            len--;
        }
        ListNode *b = tmp->next;
        tmp->next = NULL;
        head = mergeSort(head,n/2);
        b = mergeSort(b,n-n/2);
        ListNode *newHead = merge(head,b);
        return newHead;
    }
    ListNode* merge(ListNode* a,ListNode*b)
    {
        if (!a && !b)
            return NULL;
        if (!a)
            return b;
        if (!b)
            return a;
        ListNode *dummy = new ListNode(0);
        ListNode *tmp = dummy;
        while(a && b)
        {
            if (a->val<b->val)
            {
                tmp->next = a;
                a=a->next;
            }
            else
            {
                tmp->next = b;
                b=b->next;
            }
            tmp = tmp->next;
        }
        if (a)
            tmp->next = a;
        if (b)
            tmp->next = b;
        tmp = dummy->next;
        delete dummy;
        return tmp;
    }
};

146 LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

class doubleListNode
{
public:
    doubleListNode(int key_k, int value)
    {
        key = key_k;
        val = value;
        left = NULL;
        right = NULL;
    }
    doubleListNode *left;
    doubleListNode *right;
    int key;
    int val;
};
class LRUCache{
public:
    LRUCache(int capacity) {
        cache_capacity = capacity;
        size = 0;
        dummy = new doubleListNode(0,0);
        tail = dummy;
        
    }
    ~LRUCache()
    {
        delete dummy;
    }
    void insertNewNodeToHead(int key, int val);
    void removeToHead(doubleListNode * node);
    int get(int key) {
        if (mp.find(key)!=mp.end())
        {
            int res = mp[key]->val;
            removeToHead(mp[key]);
            return res;
        }
        else
            return -1;
    }
    void set(int key, int value) {
        if (mp.find(key)!=mp.end())
        {
            mp[key]->val = value;
            removeToHead(mp[key]);
        }
        else
        {
            if (size<cache_capacity)
            {
                insertNewNodeToHead(key,value);
                ++size;
            }
            else
            {
                if (tail!=dummy)
                {
                    mp.erase(tail->key);
                    tail = tail->left;
                    delete tail->right;
                }
                insertNewNodeToHead(key,value);
            }
        }
    }
    int cache_capacity;
    int size;
    unordered_map<int, doubleListNode*> mp;
    doubleListNode *dummy;
    doubleListNode *tail;
};
void LRUCache::insertNewNodeToHead(int key, int val)
{
    doubleListNode *newNode = new doubleListNode(key,val);
    newNode->right = dummy->right;
    if (dummy->right)
        dummy->right->left = newNode;
    dummy->right = newNode;
    newNode->left = dummy;
    if (tail == dummy)
        tail = dummy->right;
    mp[key]=newNode;
}
void LRUCache::removeToHead(doubleListNode * node)
{
    if (node)
    {
        if (node == tail)
        {
            tail = tail->left;
            tail->right = NULL;
        }
        else
        {
            node->left->right = node->right;
            node->right->left = node->left;
        }

        node->right = dummy->right;
        if (dummy->right)
            dummy->right->left = node;
        node->left = dummy;
        dummy->right = node;
        if (tail==dummy)
            tail = dummy->right;
    }
}

57 Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> res;
        int i=0;
        while(i<intervals.size())
        {
            if (intervals[i].end<newInterval.start)
            {
                res.push_back(intervals[i]);
            }
            else if (intervals[i].start>newInterval.end)
            {
                break;
            }
            else 
            {
                newInterval.start = min(intervals[i].start,newInterval.start);
                newInterval.end = max(intervals[i].end,newInterval.end);
            }
            i++;
        }
        res.push_back(newInterval);
        while (i<intervals.size())
        {
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};

68 Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> res;
        if (L<=0)
        {
            res.push_back("");
            return res;
        }
        if (words[0].size()<=0)
        {
            res.push_back(string(L,' '));
            return res;
        }
        int start=0;
        int end = start+1;
        bool lastLine=false;
        while(start<words.size())
        {
            int charCount=words[start].size();
            end=start+1;
            int slotCount=0;
            while(end<words.size() && (charCount+ words[end].size()+1<=L))
            {
                charCount += 1+words[end].size();
                end++;
                slotCount++;
            }
            if (end>=words.size())
                lastLine = true;
            if (lastLine)
            {
                string line = words[start];
                for (int i=start+1;i<end;i++)
                    line += ' '+words[i];
                line += string(L-line.size(),' ');
                res.push_back(line);
            }
            else if (slotCount==0)
            {
                string line = words[start];
                line += string(L-charCount,' ');
                res.push_back(line);
            }
            else
            {
                string line;
                int spaceCount = L-charCount;
                int spaceEachSlot = spaceCount/slotCount+1;
                int unevenCount = spaceCount % slotCount;
                int i=0;
                for (int j=start;j<end-1;j++)
                {
                    line+=words[j];
                    line+= string(spaceEachSlot,' ');
                    if (i<unevenCount)
                        line.push_back(' ');
                    i++;
                }
                line+=words[end-1];
                res.push_back(line);
            }
            start=end;
        }
        return res;
    }
};

43 Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

class Solution {
public:
    string multiply(string num1, string num2) {
        string n1,n2;
        for (int i=num1.size()-1;i>=0;i--)//reverse(num1.begin(),num2.end()) is better
            n1.push_back(num1[i]);
        for (int j=num2.size()-1;j>=0;j--)
            n2.push_back(num2[j]);
        
        string tmp(num1.size()+num2.size(),'0');
        for (int i=0;i<n2.size();i++)
        {
            int carry=0;
            int a = n2[i]-'0';
            for (int j=0;j<n1.size();j++)
            {
                int b = n1[j]-'0';
                int product = a*b+carry+tmp[i+j]-'0';
                int sum = product%10;
                carry = product/10;
                tmp[i+j]=sum+'0';
            }
            if (carry>0)
                tmp[i+n1.size()]=carry+'0';
        }
        string res;
        int i=tmp.size()-1;
        while(tmp[i]=='0' && i>=0)
            i--;
        if (i<0)
            return "0";
        while(i>=0)
            res.push_back(tmp[i--]);
        return res;
    }
};

5 Longest Palindrome Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution 1: Create a table. O(n^2), O(n^2)

class Solution {
public:
    string longestPalindrome(string s) {
        int max_len = 0;
        string res;
        bool matrix[s.size()][s.size()];//Vector can't pass large test case
        for (int j=0;j<s.size();j++)
        {
            for (int i=0;i<=j;i++)
            {
                if (s[i]==s[j]&& (i+1>=j-1 || matrix[i+1][j-1]))
                    matrix[i][j]=true;
                else
                    matrix[i][j]= false;
                if (matrix[i][j])
                {
                    int len = j-i+1;
                    if (len>max_len)
                    {
                        max_len = len;
                        res = s.substr(i,max_len);
                    }
                }
            }
        }
        return res;
    }
};

Solution 2: Enumerate all possible substring. O(kn), O(k), k is the size of longest palindrome

class Solution {
public:
    string longestPalindrome(string s) {
        int maxLength = 0;
        int length=0;
        string res;
        for (int i=0;i<s.size();i++){
            for (int l=i,r=i;l>=0 && r<s.size() && s[l]==s[r];l--,r++){
                length = r-l+1;
                if (length>maxLength){
                    maxLength = length;
                    res = s.substr(l,length);
                }
            }
            for (int l=i,r=i+1;l>=0 && r<s.size() && s[l]==s[r];l--,r++){
                length = r-l+1;
                if (length>maxLength){
                    maxLength = length;
                    res = s.substr(l,length);
                }
            }
        }
        return res;
        
    }
};

8 String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

class Solution {
public:
    int atoi(const char *str) {
        while (*str==' ')
            str++;
        bool negative = false;
        if (str[0]=='-')
        {
            negative = true;
            str++;
        }
        else if (str[0]=='+')
            str++;
        int res=0;
        while(*str!='\0')
        {
            if (*str>='0' && *str<='9')
            {
                if (!negative)
                {
                    if (res==INT_MAX/10 && *str>='7' || res>INT_MAX/10)
                        return INT_MAX;
                }
                else
                {
                    if (res==INT_MAX/10 && *str>='8' || res>INT_MAX/10)
                        return INT_MIN;
                }
                res = res*10 + *str-'0';
                str++;
            }
            else
            {
                break;
            }
        }
        if (negative)
            res = 0-res;
        return res;
    }
    
};

151 Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

class Solution {
public:
    void reverseWords(string &s) {
        stack<string> stk;
        int start=0;
        int end = start;
        while (end<s.size())
        {
            while(start<s.size() && s[start]==' ')
                start++;
            if (start>=s.size())
                break;
            end = start;
            while(end<s.size() && s[end]!=' ')
            {
                end++;
            }
            string tmp = s.substr(start,end-start);
            stk.push(tmp);
            start=end;
        }
        s="";
        while(!stk.empty())
        {
            s+=stk.top()+' ';
            stk.pop();
        }
        if (s.size()>1)
            s.pop_back();
    }
};

87 Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size()!=s2.size())
            return false;
        if (s1==s2)
            return true;
        string t1=s1,t2=s2;
        sort(t1.begin(),t1.end());
        sort(t2.begin(),t2.end());
        if (t1!=t2)
            return false;
        
        for (int i=1;i<s1.size();i++)
        {
            if (isScramble(s1.substr(0,i),s2.substr(0,i))&&isScramble(s1.substr(i,s1.size()-i),s2.substr(i,s2.size()-i)))
                return true;
            if (isScramble(s1.substr(0,i),s2.substr(s2.size()-i,i))&&isScramble(s1.substr(i,s1.size()-i),s2.substr(0,s2.size()-i)))
                return true;
        }
        return false;
    }
};

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2))
            return true;
        if (s1.length()!=s2.length())
            return false;
        char[] t1 = s1.toCharArray(), t2=s2.toCharArray();
        Arrays.sort(t1);
        Arrays.sort(t2);
        if (!(new String(t1)).equals(new String(t2)))
            return false;
        for (int i=1;i<s1.length();i++){
            if (isScramble(s1.substring(0,i), s2.substring(0,i)) && isScramble(s1.substring(i),s2.substring(i)))
                return true;
            if (isScramble(s1.substring(0,i),s2.substring(s2.length()-i)) && isScramble(s1.substring(i),s2.substring(0,s2.length()-i)))
                return true;
        }
        return false;
    }
}

95 Unique Binary Search Trees II

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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        vector<TreeNode*> res;
        help(1,n,res);
        return res;
    }
    void help(int first,int last,vector<TreeNode*>& res)
    {
        if (first>last)
        {
            res.push_back(NULL);
            return;
        }
        for (int i=first;i<=last;i++)
        {
            vector<TreeNode*> leftChild,rightChild;
            help(first,i-1,leftChild);
            help(i+1,last,rightChild);
            for (int j=0;j<leftChild.size();j++)
            {
                for (int k=0;k<rightChild.size();k++)
                {
                    TreeNode* root = new TreeNode(i);
                    root->left = leftChild[j];
                    root->right = rightChild[k];
                    res.push_back(root);
                }
            }
        }
    }
};

10 Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

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

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*s=='\0')
        {
            while(strlen(p)>=2 && *(p+1)=='*')
                p+=2;
            return *p=='\0';
        }
        if (*p=='\0')
        {
            return *s=='\0';
        }
        if (strlen(p)==1)
            return (strlen(s)==1) && (*s==*p || *p=='.');
        if (*(p+1)!='*')
        {
            if (*s==*p || *p=='.')
                return isMatch(s+1,p+1);
            return false;
        }
        else
        {
            if (isMatch(s,p+2))
                return true;
            if (*s==*p || *p=='.')
                return isMatch(s+1,p);
            return false;
        }
    }
};