161 One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size()<t.size())
            return isOneEditDistance(t,s);
        if (s.size()-t.size()>=2)
            return false;
        if (s.size()==t.size())
            return sameSize(s,t);
        else
            return oneSizeDif(s,t);
    }
    bool sameSize(const string &s,const string &t)
    {
        for (int i=0;i<s.size();i++)
        {
            if (s[i]!=t[i])
                return s.substr(i+1)==t.substr(i+1);
        }
        return false;
    }
    bool oneSizeDif(const string &s, const string &t)
    {
        for (int i=0;i<t.size();i++)
        {
            if (s[i]!=t[i])
            {
                return s.substr(i+1)==t.substr(i);
            }
        }
        return true;
    }
};

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

Solution 1: 2 dimensional matrix:

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

Solution 2: 1 dimensional vector

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

132 Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

class Solution {
public:
    int minCut(string s) {
        if (s.size()<=1)
            return 0;
        vector<int> res = vector<int>(s.size(),0);
        bool palindrome[s.size()][s.size()];
        for (int i=0;i<s.size();i++)
            for (int j=0;j<s.size();j++)
                palindrome[i][j]=true;
        for (int j=0;j<s.size();j++)
        {
            for (int i=0;i<j;i++)
            {
                if (!(s[j]==s[i] && (i+1>=j-1 || palindrome[i+1][j-1])))
                    palindrome[i][j]=false;
            }
        }
        for (int i=0;i<s.size();i++)
        {
            int cut=INT_MAX;
            for (int j=0;j<=i;j++)
            {
                if (palindrome[j][i])
                {
                    cut = min(cut,(j>=1?res[j-1]:0)+1);
                }
            }
            res[i]=cut;
        }
        return res[s.size()-1]-1;
    }
    
};

164 Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

class Solution {
public:
    int maximumGap(vector<int> &num) {
        int n = num.size();
        if (n<=1)
            return 0;
        int maxVal = num[0],minVal = num[0];
        for (int i=1;i<n;i++)
        {
            maxVal = max(maxVal,num[i]);
            minVal = min(minVal,num[i]);
        }
        
        int step = (maxVal-minVal)/(n)+1;
        int numberBucket = (maxVal-minVal)/step+1;
        vector<int> minVec = vector<int>(numberBucket,INT_MAX);
        vector<int> maxVec = vector<int>(numberBucket,INT_MIN);
        for (int i=0;i<n;i++)
        {
            int index = (num[i]-minVal)/step;
            minVec[index] = min(minVec[index],num[i]);
            maxVec[index] = max(maxVec[index],num[i]);
        }
        int res = 0;
        int last = 0;
        for (int i=0;i<numberBucket;i++)
        {
            if (minVec[i]==INT_MAX && maxVec[i]==INT_MIN)
                continue;
            res = max(maxVec[i]-minVec[i],res);
            if (i>0)
                res = max(res,minVec[i]-maxVec[last]);
            last = i;
        }
        return res;
            
    }
};

190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res;
        for (int i=0;i<32;i++)
        {
            res = res<<1 | (n&1);
            n = n>>1;
        }
        return res;
    }
};

44 Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char * star=NULL;
        const char * star_s = s;
        while(*s)
        {
            if (*s==*p || *p=='?')
            {
                s++;
                p++;
                continue;
            }
            else if (*p=='*')
            {
                star = p;
                star_s = s;
                p++;
                continue;
            }
            else if (star)
            {
                s=++star_s;
                p=star+1;
            }
            else
                return false;
        }
        while(*p=='*')
            p++;
        return !*p;
        
    }
};

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;
        while(res<n)
        {
            int readNumber = read4(buf+res);
            res+= readNumber;
            if (readNumber<4)
                break;
        }
        if (res>n)
        {
            buf[n]='\0';
            res = n;
        }
        return res;
    }
};

158 Read N Characters Given Read4 II - Call multiple times

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 may be called multiple times.

// 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
     */
     Solution(){
         start=0;end=0;
     }
     bool isEmpty(){
         return start==end;
     }
    int read(char *buf, int n) {
        int res=0;
        while(res<n && !isEmpty()){
            buf[res]=buffer[start];
            start++;
            start %=5;
            res++;
        }
        while(res<n){
            int count = read4(buf+res);
            res += count;
            if (count<4)
                break;
        }
        if (res>n){
            for (int i=n;i<res;i++){
                buffer[end]=buf[i];
                end = (end+1)%5;
            }
            res = n;
        }
        return res;
    }
private:
    int buffer[5];
    int start;
    int end;
};

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) {
        int len=0;
        unordered_map<char,int> mp;
        int count=0;
        int start=0,end=0;
        while(end<s.size())
        {
            if (mp.find(s[end])==mp.end())
            {
                if (count<2)
                {
                    mp[s[end]]=end;
                    count++;
                }
                else
                {
                    count++;
                    while(count>2)
                    {
                        if (mp.find(s[start])!=mp.end())
                        {
                            if (mp[s[start]]==start)
                            {
                                mp.erase(s[start]);
                                count--;
                            }
                        }
                        start++;
                    }
                    mp[s[end]]=end;
                }
            }
            else
            {
                mp[s[end]]=end;
            }
            len = max(len,end-start+1);
            end++;
        }
        return len;
    }
};

3 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = 0;
        unordered_map<char,int> mp;
        int start=0;
        int end = start;
        while(end<s.size())
        {
            if (mp.find(s[end])!=mp.end())
            {
                start = max(start,mp[s[end]]+1);
                mp[s[end]]=end;
            }
            else
            {
                mp[s[end]]=end;
            }
            len = max(len,end-start+1);
            end++;
        }
        return len;
    }
};

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

/**
 * 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* dummy =new ListNode(0);
        dummy->next = head;
        int val = INT_MIN;
        ListNode *cur = head;
        ListNode* pre = dummy;
        while(cur)
        {
            if (cur->val == val || cur->next && cur->val == cur->next->val)
            {
                pre->next = cur->next;
                val = cur->val;
                delete cur;
                cur=pre->next;
            }
            else
            {
                val = cur->val;
                pre = cur;
                cur = cur->next;
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};