Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Problem link

Solution

  • calculate from right to left
class Solution {
public:
    string addBinary(string a, string b) {
        if (a.empty()) return b;
        if (b.empty()) return a;
        int m = a.size();
        int n = b.size();
        string c;
        bool carry=false;
        int i,j;
        int sum;
        for (i=m-1, j=n-1; i>=0 && j>=0; --i, --j){
            sum = a[i]-'0' + b[j]-'0' + carry;
            carry = sum/2? true:false;
            c = to_string(sum%2) + c;
        }
        if (j>=0){ // run out of a
            for (; j>=0; --j){
                sum = b[j]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }else if (i>=0){ // run out of b
            for (; i>=0; --i){
                sum = a[i]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }
        if (carry==1){
            c = "1" + c;
        }
        return c;
    }
};
Advertisements
Add Binary

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Problem link

Solution

  • careful about the order of strings added to the output
class Solution {
public:
    string countAndSay(int n) {
        string in="1";
        for (int i=1; i<n; i++){
            in = helper(in);
        }
        return in;
    }
    
    string helper(string &in) {
        string out;
        char c = in[0];
        int count=1;
        char countChar;
        for (int i=1; i<in.size(); i++) {
            if (in[i]==c) {
                count++;
            } else {
                countChar = count+'0';
                out = out + countChar;
                out = out + c;
                c = in[i];
                count = 1;
            }
        }
        countChar = count+'0';
        out = out + countChar;
        out = out + c;
        return out;
    }
};
Count and Say

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.

Problem link

Solution

  • from S, take subsequences that is T, i.e., how many ways that some characters in S can be deleted so that the rest of characters is T
  • S[i]!=T[j], the last elements in both strings can ignored, dp[i][j]  = dp[i-1][j-1]
  • S[i] == T[j], S[i] is used to get T[j] (dp[i-1][j-1]) + S[i] is not used to get T[j] (dp[i-1][j-1])
class Solution {
public:
    int numDistinct(string S, string T) {
        vector<vector<int>> dp(S.size()+1, vector<int>(T.size()+1));
        for (int i=0; i<=S.size(); ++i){
            dp[i][0] = 1;
        }
        for (int i=1; i<=T.size(); ++i){
            dp[0][i] = 0;
        }
        for (int i=1; i<=S.size(); ++i){
            for (int j=1; j<=T.size(); ++j){
                if (S[i-1]!=T[j-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[S.size()][T.size()];
    }
};

Using 1D array

  • couldn’t eliminate the first dimension because [i-1, j-1] will get overwritten from out loop
class Solution {
public:
    int numDistinct(string S, string T) {
        vector<int> dp(S.size()+1, 1); // get rid of the second dimension
        for (int j=1; j<=T.size(); ++j){
            int upleft = dp[0];
            dp[0] = 0;
            for (int i=1; i<=S.size(); ++i){
                int tmp = dp[i];
                if (S[i-1]==T[j-1]){
                    dp[i] = upleft + dp[i-1];
                }else{
                    dp[i] = dp[i-1];
                }
                upleft = tmp;
            }
        }
        return dp[S.size()];
    }
};
Distinct Subsequences

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Problem link

Solution

  • use hash table to reduce the problem into finding longest subsequence using DP
  • Memory Limit Exceeded due to the extra memory use
class Solution
{
public:
    int minDistance(string word1, string word2) {
        if (word1.empty()) return word2.size();
        if (word2.empty()) return word1.size();
        unordered_map<char, queue<int>> m;
        int i;
        unordered_map<char, queue<int>>::const_iterator got;
        // when there are duplicates, there are ordered increasingly in the map
        for (i=0; i<word1.size(); ++i) {
            got = m.find(word1[i]);
            if (got == m.end()) {
                queue<int> q;
                q.push(i);
                m[word1[i]] = q;
            } else {
                m[word1[i]].push(i);
            }
        }
        vector<pair<int, int>> idx; // need to store both here
        // whenever there is a found, delete the key in the hashmap
        for (i=0; i<word2.size(); ++i) {
            got = m.find(word2[i]);
            if (got != m.end()) {
                idx.push_back(make_pair(m[word2[i]].front(), i));
                m[word2[i]].pop();
                if ((got->second).empty()) {
                    m.erase(got);
                }
            }
        }
        if (idx.empty()) return max(word1.size(), word2.size());

        // find all longest increasing subsequence in idx, which can be sovled by DP
        // l[i] = max(l[j])+1 for idx[j]<idx[i]
        // 2D DP using 1D array
        vector<int> l(idx.size(), 1);
        // store the indices of idx.first
        // 1 dimension: corresponses to each element in idx
        // 2 & 3 dimensions: there can be multiple longest sequences related to each element
        vector<vector<vector<int>>> vvv (idx.size(),vector<vector<int>>());
        int j;
        int maxl;
        vector<int> maxidx;
        for (i=0; i<idx.size(); ++i) {
            maxl = i>0 ? l[i-1]:1; // inherent previous longest sequence
            for (j=0; j<i; ++j) {
                // be careful about the case where longest increasing subsequence is 1
                if (idx[j].first<idx[i].first) {
                    if (l[j]+1>maxl) {
                        maxl = l[j]+1;
                        maxidx.clear();
                        maxidx.push_back(j);
                        // printf("better: maxidx push j %d\n", j);
                    } else if (l[j]+1==maxl) {
                        maxidx.push_back(j);
                        // printf("equal: maxidx push j %d\n", j);
                    }
                }
            }
            l[i] = maxl;
            // add each to each sequence in vv, add i at the end of each sequence
            if (!maxidx.empty()){
                // printf("maxidx not empty\n");
                for (j=0; j<maxidx.size(); ++j){
                    for (int k=0; k<vvv[j].size(); ++k){
                        vvv[i].push_back(vvv[j][k]);
                        vvv[i].back().push_back(i); // add the last element
                    }
                }
            }else{
                vector<vector<int>> vv;
                vector<int> v;
                v.push_back(i);
                vv.push_back(v);
                vvv[i] = vv;
            }
        }
        vector<vector<int>> vv = vvv.back();
        // find minimal edit distance from all longest subsequence
        int I;
        int preI;
        int minE = INT_MAX;
        int dist;
        for (i=0; i<vv.size(); ++i) {
            dist = 0;
            for (j=0; j<vv[0].size(); ++j) {
                I = vv[i][j];
                if (j==0) {
                    dist += max(idx[I].first, idx[I].second);
                } else if (0<j && j<vv[0].size()) { // inbetween
                    preI = vv[i][j-1];
                    dist += max(idx[I].first-idx[preI].first-1, idx[I].second-idx[I].second-1);
                }
            }
            dist += max(word1.size()-idx.back().first-1, word2.size()-idx.back().second-1);
            minE = min(dist, minE);
        }
        return minE;
    }

};

Direct DP solution

  • applying the DP directly to the strings
  • problem: how to find matching initially?
  • it is quite similar to the longest common subsequence problem (LCS), rather than LCS, here we store the edit distance up to word1[i] and word2[j] at [i][j]
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1));
        // first row
        for (int i=0; i<=word1.size(); ++i){
            dp[i][0] = i;
        }
        // first column
        for (int i=1; i<=word2.size(); ++i){
            dp[0][i] = i;
        }
        for (int i=1; i<=word1.size(); ++i){
            for (int j=1; j<=word2.size(); ++j){
                dp[i][j] = dp[i-1][j-1];
                if (word1[i-1]!=word2[j-1]){
                    ++dp[i][j];
                    dp[i][j] = min(min(dp[i][j-1]+1, dp[i][j]), dp[i-1][j]+1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
Edit Distance

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.

Problem link

Solution

  • greedy algorithm O(n) wouldn’t work, for instance, “aaabaa”
  • two DP problems: 1. find the min cut; 2. check palindrome
  • reference: http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning-ii.html
class Solution {
public:
    int minCut(string s) {  
            int len = s.size();  
            int D[len+1]; 
            bool P[len][len];  
            // auxilary storage initialization
            for(int i = 0; i <= len; i++){ // D[i] is the min cut between i:n
                //the worst case is cutting by each char  
                D[i] = len-i; 
            }
            for(int i = 0; i < len; i++){
                for(int j = 0; j < len; j++){
                    P[i][j] = false;        
                }    
            }
            for(int i = len-1; i >= 0; i--){// from last to first to reuse
                for(int j = i; j < len; j++){  
                      if(s[i] == s[j] && (j-i<2 || P[i+1][j-1])){  
                           P[i][j] = true;  
                           D[i] = min(D[i],D[j+1]+1);  
                      }  
                 }  
            }  
            return D[0]-1;  
      }  
};

A solution with O(n) extra space

  • cut[i] store the min cut for the first i elements
  • advancing the pivot node i
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> cut(n+1, 0);  // number of cuts for the first k characters
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

            for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
        }
        return cut[n];
    }
};
Palindrome Partitioning II

Longest Palindromic 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.

Problem link

Solution

  • 2D dynamic programming
class Solution {
public:
    string longestPalindrome(string s) {
        int n = 0;
        int start;
        bool pal[1000][1000] = {false};
        for (int i=s.size()-1; i>=0; --i){
            // reverse the order of i so that shorter subtrings are considered first
            for (int j=i; j<s.size(); ++j){
                if ((i+1>=j-1||pal[i+1][j-1]) && s[i]==s[j]){
                    pal[i][j] = true;
                    if (n<j-i+1){
                        n = j-i+1;
                        start=i;
                    }
                } 
            }
        }
        return s.substr(start, n); 
    }
};
Longest Palindromic Substring

Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Problem link

Solution

  • progressively increase the size of substrings
  • use simple recursion, yet there are lots of duplication checks
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> vv;
        if (s.empty()) return vv;
        vector<string> v;
        rec(vv, v, s, 0, s.size()-1);
        return vv;
    }
    
    void rec(vector<vector<string>> &vv, vector<string> &v, string &s, int l, int r){
        for (int i=l; i<=r; ++i){
            string str = s.substr(l, i-l+1);
            if (check(str)){ // if pass the test
                v.push_back(str);
                if (i+1<=r){
                    rec(vv, v, s, i+1, r);
                }else{ // i==r
                    vv.push_back(v);
                }
                v.pop_back();
            }
        }
    }
    
    bool check(string &s){
        // check if the string is a palindrome
        int l = 0;
        int r = s.size()-1;
        while (l<=r){
            if (s[l]!=s[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
};

An improved solution

  • saving the palindrome answers in a matrix
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> vv;
        vector<string> v;
        vector<vector<bool>> pal(s.size(), vector<bool>(s.size(), false));
        // two pointer method
        for (int i=s.size()-1; i>=0; --i){ 
            // reverse the order of i so that shorter subtrings are considered first
            for (int j=i; j<s.size(); ++j){
                if (s[i]==s[j] && (i+1>=j-1||pal[i+1][j-1])) pal[i][j] = true;
            }
        }
        rec(vv, v, s, pal, 0);
        return vv; 
    }
    
    void rec(vector<vector<string>> &vv, vector<string> &v, string &s, vector<vector<bool>> &pal, int l){
        for (int i=l; i<= s.size()-1; ++i){
            if (pal[l][i]){ // if pass the test
                v.push_back(s.substr(l, i-l+1));
                if (i+1<=s.size()-1){
                    rec(vv, v, s, pal, i+1);
                }else{ // i==r
                    vv.push_back(v);
                }
                v.pop_back();
            }
        }
    }
};
Palindrome Partitioning