Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Problem link

Solution

  • backtrack with stack
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector< vector<int> > vv;
        int i;
        unsigned n=num.size();
        vector<int> v;
        vector<bool> used(n, false);

        i=0;
        while (true){
            // only stop the loop when it is at level zero and i goes over
            v.push_back(i);
            used[i]=true;
            for (i=0; i<n; i++){// looks for next available position to select
                if (used[i]==false){
                    break;
                }
            }
            if (v.size()==n){
                // a complete sequence is generated, backtrack
                vector<int> tmp;
                for (int j=0; j<v.size(); j++){
                    tmp.push_back(num[v[j]]);
                }
                vv.push_back(tmp);
                int j;
                do{
                    j=v.back();
                    v.pop_back();
                    used[j]=false;
                    for (++j; j<n; ++j){// starting from current indices, looks for next available position to select
                        if (used[j]==false){
                        break;
                        }
                    }
                }while(j>=n&&!v.empty()|| (j<n&&used[j]));
                if (j>=n&&v.empty()){
                    break;
                }
                i=j;
            }
        }
        return vv;
    }
};

Recursive solution

  • use an auxiliary array to track whether the current element has been used in the current permutation
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> vv;
        vector<bool> u(num.size(), false); // used or 
        vector<int> v;
        rec(vv, v, u, num);
        return vv;
    }
    
    void rec(vector<vector<int>> &vv, vector<int> &v, vector<bool> &u, vector<int> &num){
        for (int i=0; i<num.size(); i++){
            if (!u[i]){ // if i is not used
                v.push_back(num[i]);
                u[i] = true;
                if (v.size()==num.size()){
                    vv.push_back(v);
                }else{
                    rec(vv, v, u, num);
                }
                v.pop_back();
                u[i] = false;
            }
        }
    }
};
Permutations

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

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Problem link

Solution

  • find the station with maximum difference, M, start from there. Because if it is possible from reach M from some other station, there must be gas left. It is sufficient but not necessary
  • save partial path in array, to avoid going over and over again
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int modi = gas.size()-1;
        int start = gas.size()-1;
        int left = 0;
        while (true){
            while ((left += gas[modi] - cost[modi])>=0){
                modi++;
                modi = modi % gas.size();
                if (modi == start){
                    return left>=0? start: -1;
                }
            }
            start--;
            if (start<0) return -1;
            if (modi == start){
                return left>=0? start: -1;
            }
            while ((left+= gas[start] - cost[start])<0 || gas[start] - cost[start]<0 ){
                start--;
                if (start<0) return -1;
                if (modi == start){
                    return left>=0? start: -1;
                }
            }
            modi++;
            modi = modi % gas.size();
            if (modi == start){
                return left>=0? start: -1;
            }
        }
        return -1;
    }
};

An improved solution

  • after one scan, if totalSum>0 and curSum>0, the sum of right of start < 0, curSum should be enough to support a cyclic visit
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int totalGas = 0;
        int curGas = 0;
        int start = 0;
        int diff;
        for (int i=0; i<gas.size(); ++i){
            diff = gas[i] - cost[i];
            curGas += diff;
            totalGas += diff;
            if (curGas<0){
                start = i+1;
                curGas = 0;
            }
        }
        return totalGas<0 ? -1:start;
    }
};
Gas Station

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

Insertion Sort List

Sort a linked list using insertion sort.

Problem link

Solution

  • insertion sort: the sub-array on the left are sorted, new elements are inserted into the proper position on the left
  • need to search from head every time for the new node to find a place to insert
  • quite complicated, runs slower and painful to debug…
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *p1 = NULL, *cur, *ret = head, *next, *p2=NULL;
        while (head){
            cur = ret;
            while (cur!=head && cur->val <= head->val){
                p1 = cur;
                cur = cur->next;
            }
            if (cur!=ret){
                if (cur!=head){ // p1->val < head->val < cur->val
                    // insert between p1 and cur
                    next = head->next;
                    p1->next = head;
                    head->next  = cur;
                    head = next;
                    if (p2){
                        p2->next = next;
                    }
                }else{
                    p2 = head;
                    head = head->next;
                }
            }else{ // insert before ret/cur, head node replaces the old head
                if (cur->val > head->val){
                    next = head->next;
                    head->next = cur;
                    ret = head;
                    head = next;
                    if (p2){
                        p2->next = next;
                    }
                }else{ // no need to delete/insert node
                    p2 = head;
                    head = head->next;
                }
            }
        }
        return ret;
    }
};

Dummy head ndoe solution

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode* dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode* left;
        ListNode* tmp;
        head = dummy;
        while (head && head->next){ // evaluting next node to avoid storing the pre pointer
            left = dummy;
            while (head->next->val > left->next->val){
                left = left->next;
            }
            if (head->next!=left->next){ // insert head right before left
                // first delete head->next
                tmp = head->next;
                head->next = head->next->next;
                // insert head->next between left and left->next
                tmp->next = left->next;
                left->next = tmp;
            }else{
                head = head->next;    
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Insertion Sort List

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Problem link

Solution

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string>> vv;
        vector<int> v;
        rec(vv, v, n);
        return vv;
    }
    
    void rec(vector<vector<string>> &vv, vector<int> &v, int n){
        for (int i=0; i<n; ++i){
            if (!conflict(v, i)){
                v.push_back(i);
                if (v.size()==n){
                    vv.push_back(conv(v));
                }else{
                    rec(vv, v, n);
                }
                v.pop_back();
            }
        }
    }
    
    vector<string> conv(vector<int> &v){
        int n=v.size();
        vector<string> vs(n, string(n,'.'));
        for (int i=0; i<n; ++i){
            vs[i][v[i]] = 'Q';
        }
        return vs;
    }
    
    bool conflict(vector<int> &assign, int new_queen){
        // check for conflict with all previously existing queens
        for (int i=0; i<assign.size(); i++){
            if (assign[i]==new_queen || assign.size()-i == abs(new_queen - assign[i])){
                return true;
            }
        }
        return false;
    }
};
N-Queens