140. Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].


class Solution {
   unordered_map<string, vector<string>> m;

   public:
    vector<string> wordBreak(string s, unordered_set<string>& dict) {
        if (s.empty()) {
            return {};
        }
        if (m.count(s)) {
            return m[s];
        }
        vector<string> ret;
        if (dict.count(s)) {
            ret.push_back(s);
        }
        for (int i = 1; i < s.length(); ++i) {
            const string end = s.substr(i);
            if (dict.count(end)) {
                const auto &front = wordBreak(s.substr(0, i), dict);
                if (!front.empty()) {
                    const vector<string> new_sols = combine(front, end);
                    ret.insert(ret.end(), new_sols.begin(), new_sols.end());
                }
            }
        }
        m[s] = ret;
        return ret;
    }

    vector<string> combine(const vector<string> &front, const string &end) {
        vector<string> ret;
        for (const string &v : front) {
            ret.push_back(v + " " + end);
        }
        return ret;
    }
};

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.



struct Node {
  int k = -1;
  int v = -1;
  Node *next = nullptr;
  Node *front = nullptr;
};

class LRUCache{
public:
    LRUCache(int capacity) : cap_(capacity) {
        link(&begin, &end);
    }

    int get(int key) {
        if (!m.count(key)) {
            return -1;
        }
        Node *n = m.at(key);
        Pop(n);
        Add(end.front, &end, n);
        return n->v;
    }

    void link(Node *a, Node *b) {
        a->next = b;
        b->front = a;
    }

    void Pop(Node *n) {
        link(n->front, n->next);
        m.erase(n->k);
    }

    void Add(Node *front, Node *next, Node *n) {
        link(front, n);
        link(n, next);
        m[n->k] = n;
    }

    void AddToEnd(Node *n) {
        Add(end.front, &end, n);
    }

    void set(int key, int value) {
        if (m.count(key)) {
            Node *n = m.at(key);
            n->v = value;
            get(key); // Move it to the end. Set counts as one visit.
        } else {
            Node *n = new Node;
            n->k = key;
            n->v = value;
            if (m.size() >= cap_) {
                Pop(begin.next);
            }
            AddToEnd(n);
        }
    }

    int cap_;
    unordered_map<int, Node*> m;
    Node begin;
    Node end;
};

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

  class MinStack {
   public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        data_.push_back(x);
        const int pos = data_.size() - 1;
        if (min_.empty()) {
            min_.push_back(pos);
        } else if (getMin() > x) {
            min_.push_back(pos);
        }
    }

    void pop() {
        const int pos = data_.size() - 1;
        data_.pop_back();
        if (pos == *min_.rbegin()) {
            min_.pop_back();
        }
    }

    int top() {
        return *data_.rbegin();
    }

    int getMin() {
        return data_.at(*min_.rbegin());
    }

    vector<int> data_;
    vector<int> min_;
};

413. Arithmetic Slices

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

My solution based on MATH.


  class Solution {
   public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if (A.size() < 3) {
            return 0;
        }
        vector<int> can;
        for (int i = 0; i < A.size() - 2;) {
            if (!isCandi(A, i)) {
                ++i;
                continue;
            }
            int len = findSeq(A, i);
            can.push_back(len);
            i += len - 1;
        }
        return sum(can);
    }

    bool isCandi(const vector<int> &A, int i) {
        return A[i+1] - A[i] == A[i+2] - A[i+1];
    }

    int findSeq(const vector<int> &A, int i) {
        const int dis = A[i+1] - A[i];
        int j = i + 1;
        for (; j < A.size() && dis == A[j] - A[j-1]; ++j) {
        }
        return j - i;

    }

    int sum(const vector<int> &candi) {
        int ret = 0;
        for (const int v : candi) {
            ret += (v-1)*(v-2) / 2;
        }
        return ret;
    }
};

Web solution based on Dynamic Programming.


class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        if (n < 3) return 0;
        // dp[i] means the number of arithmetic slices ending with A[i]
        vector<int> dp(n, 0);
        // if the first three numbers are arithmetic or not
        if (A[2]-A[1] == A[1]-A[0]) dp[2] = 1;
        int result = dp[2];
        for (int i = 3; i < n; ++i) {
            // if A[i-2], A[i-1], A[i] are arithmetic,
            // then the number of arithmetic slices ending with A[i] (dp[i])
            // equals to:
            //      the number of arithmetic slices ending with A[i-1] (dp[i-1],
            //      all these arithmetic slices appending A[i] are also arithmetic)
            //      +
            //      A[i-2], A[i-1], A[i] (a brand new arithmetic slice)
            // it is how dp[i] = dp[i-1] + 1 comes
            if (A[i]-A[i-1] == A[i-1]-A[i-2])
                dp[i] = dp[i-1] + 1;
            result += dp[i]; // accumulate all valid slices
        }
        return result;
    }
};

446. Arithmetic Slices II - Subsequence QuestionEditorial Solution

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if (A.size() < 3) {
            return 0;
        }
        int ret = 0;
        // index -> diff -> count.
        // Number of Arithmetic slices ending at index, with diff, min length is 2.
        vector<unordered_map<int, int>> dp(A.size());
        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                const long bound = long(A[i]) - long(A[j]);
                if (bound >= INT_MAX || bound <= INT_MIN) {
                    continue;
                }
                const int diff = A[i] - A[j];
                dp[i][diff] += 1;
                if (dp[j].count(diff)) {
                    dp[i][diff] += dp[j][diff];
                    ret += dp[j][diff];
                }
            }
        }
        return ret;
    }
};

397. Integer Replacement QuestionEditorial Solution

Given a positive integer n and you can do operations as follow:

  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

class Solution {
public:
    int integerReplacement(int n) {
        // Check tails:
        //   00 -> /2
        //   10 -> /2
        //   11 -> +1
        //   01 -> -1
        if (n == 1) {
            return 0;
        }
        if (n == 0) {
            return INT_MAX;
        }
        if (n == INT_MAX) {
            return 32;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        const int last = (n & 3);
        if (last == 3) {
            return integerReplacement(n + 1) + 1;
        } else if (last == 1) {
            return integerReplacement(n - 1) + 1;
        }
        return integerReplacement(n / 2) + 1;
    }
};

395. Longest Substring with At Least K Repeating Characters QuestionEditorial Solution

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

class Solution {
public:
    int longestSubstring(string s, int k) {
        return divideAndConqur(s, 0, s.size(), k);
    }

    // It takes O(logn) iterations and each iteration takes O(n) so the time
    // complexity is O(nlogn).
    int divideAndConqur(const string &s, int b, int e, int k) {
        if ((e - b) < k) {
            return 0;
        }
        int cnt[26]{}; // Initialize all to 0.
        for (int i = b; i < e; ++i) {
            const int val = s[i] - 'a';
            cnt[val] += 1;
        }
        for (int i = b; i < e; ++i) {
            const int val = s[i] - 'a';
            if (cnt[val] < k) {
                // If we found one element whose total < k, then any sub string containing
                // that element cannot be taken into consideration.
                return max(divideAndConqur(s, b, i, k), divideAndConqur(s, i+1, e, k));
            }
        }
        return e - b;
    }
};

Thanks to wfxr for enlightening.

One O(n) time complexity solution is here, but it consumes O(n) extra memory as well.

314. FACEBOOK Binary Tree Vertical Order Traversal

Nice and short solution

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples:

  1. Given binary tree [3,9,20,null,null,15,7],
       3
      /\
     /  \
     9  20
        /\
       /  \
      15   7
    

    return its vertical order traversal as:

    [
      [9],
      [3,15],
      [20],
      [7]
    ]
    
  2. Given binary tree [3,9,8,4,0,1,7],
         3
        /\
       /  \
       9   8
      /\  /\
     /  \/  \
     4  01   7
    

    return its vertical order traversal as:

    [
      [4],
      [9],
      [3,0,1],
      [8],
      [7]
    ]
    
  3. Given binary tree [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5),
         3
        /\
       /  \
       9   8
      /\  /\
     /  \/  \
     4  01   7
        /\
       /  \
       5   2
    

    return its vertical order traversal as:

    [
      [4],
      [9,5],
      [3,0,1],
      [8,2],
      [7]
    ]
    

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

    struct Size {
        int left;
        int right;
    };

    Size GetColumnSize(TreeNode *root) {
        if (root == nullptr) {
            return Size{0, 0};
        }
        const Size &left = GetColumnSize(root->left);
        const Size &right = GetColumnSize(root->right);
        return Size {
            std::max(left.left + 1, right.left - 1),
            std::max(left.right - 1, right.right + 1)
        };
    }

    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) {
            return ret;
        }
        const Size &size = GetColumnSize(root);
        ret.resize(size.left + size.right - 1, {});
        // Traverse using queue.
        std::queue<NodeColumn> trav;
        trav.push(NodeColumn{root, size.left - 1});
        while (!trav.empty()) {
            const NodeColumn &current = trav.front();
            trav.pop();
            ret[current.col].push_back(current.node->val);
            if (current.node->left) {
                trav.push(NodeColumn{current.node->left, current.col - 1});
            }
            if (current.node->right) {
                trav.push(NodeColumn{current.node->right, current.col + 1});
            }

        }
        return ret;
    }
};

273. Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Good solution


class Solution {
public:

    void trim(string *str) {
        while (*str->rbegin() == ' ') {
            str->pop_back();
        }
    }

    string join(const vector<string> &input) {
        string ret;
        for (const string &t : input) {
            if (!t.empty()) {
                ret.append(t);
                ret.append(" ");
            }
        }
        trim(&ret);
        return ret;
    }

    string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        static const vector<string> split = {
            "",
            "Thousand",
            "Million",
            "Billion",
            "Trillion"
        };
        vector<string> all_tokens;
        int i = 0;
        while (num > 0) {
            const int under_thou = num - (num / 1000) * 1000;
            num /= 1000;
            const string &token = BelowThousand(under_thou);
            if (!token.empty()) {
                all_tokens.push_back(join({
                    token, split[i]
                }));
            }
            ++i;
        }
        std::reverse(all_tokens.begin(), all_tokens.end());
        return join(all_tokens);
    }


    string TokenTranslate(int num) {
        static const map<int, string> mapping = {
            {0, ""},
            {1, "One"},
            {2, "Two"},
            {3, "Three"},
            {4, "Four"},
            {5, "Five"},
            {6, "Six"},
            {7, "Seven"},
            {8, "Eight"},
            {9, "Nine"},
            {10, "Ten"},
            {11, "Eleven"},
            {12, "Twelve"},
            {13, "Thirteen"},
            {14, "Fourteen"},
            {15, "Fifteen"},
            {16, "Sixteen"},
            {17, "Seventeen"},
            {18, "Eighteen"},
            {19, "Nineteen"},
            {20, "Twenty"},
            {30, "Thirty"},
            {40, "Forty"},
            {50, "Fifty"},
            {60, "Sixty"},
            {70, "Seventy"},
            {80, "Eighty"},
            {90, "Ninety"}
        };
        return mapping.at(num);
    }

    string BelowHundred(int num) {
        // num < 100.
        if (num < 20) {
            return TokenTranslate(num);
        }
        int tens = (num / 10) * 10;
        return join({
            TokenTranslate(tens), TokenTranslate(num - tens)
        });
    }

    string BelowThousand(int num) {
        // num < 1000.
        if (num < 100) {
            return BelowHundred(num);
        }
        return join({
            BelowHundred(num / 100), "Hundred", BelowHundred(num - (num / 100) * 100)
        });
    }
};

410. Split Array Largest Sum BAIDU

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        if (nums.empty()) {
            return 0;
        }
        if (nums.size() < m) {
            return 0;
        }
        long max = sum(nums);
        long min = MaxVal(nums);
        while (min < max) {
            const long mid = (min + max) / 2;
            if (IsValid(nums, m, mid)) {
                // It is valid to find a partition of m sub arrays with the
                // largest sum <= mid.
                // In this case, we should try a smaller mid to see whether
                // there are better solutions.
                max = mid;
            } else {
                // We increase mid to see whether there is valid solution.
                min = mid + 1;
            }
        }
        return min;
    }

    // Returns true if there is one partition of m with the largest sum <= max.
    // This function can be done in O(n).
    bool IsValid(const vector<int> &n, int m, long max) {
        long sum = 0;
        int group = 1;
        for (const int i : n) {
            if (sum + i <= max) {
                // Put as many element as possible into previous partition.
                sum += i;
            } else {
                // The previous partition ends, start a new partition.
                sum = i;
                ++group;
            }
            if (group > m || sum > max) {
                return false;
            }
        }
        return true;
    }

    // Sum of vectors, using long because int will over flow.
    long sum(const vector<int> &n) {
        long ret = 0;
        for (const int i : n) {
            ret += i;
        }
        return ret;
    }

    // The max value in the vector.
    int MaxVal(const vector<int> &n) {
        int ret = 0;
        for (const int i : n) {
            ret = std::max(ret, i);
        }
        return ret;
    }
};

161. One Edit Distance SNAPCHAT

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.empty() || t.empty()) {
            return s.size() + t.size() == 1;
        }
        if (s.size() == t.size()) {
            // When the two has the same size, check whether only one char differs.
            int diff = 0;
            for (int i = 0; i < s.size() && diff <= 1; ++i) {
                // Put diff <= 1 here to early terminate the loop.
                if (s.at(i) != t.at(i)) {
                    ++diff;
                }
            }
            return diff == 1;
        }
        // Find the shorter string.
        const string &small = s.size() < t.size() ? s : t;
        const string &large = s.size() < t.size() ? t : s;
        if (small.size() + 1 != large.size()) {
            // If the two has distance not equal to one, false.
            return false;
        }
        for (int i = 0; i < small.size(); i++) {
            if (small.at(i) != large.at(i)) {
                // Find the first character mismatch, than compare the following characters.
                return small.substr(i) == large.substr(i + 1);
            }
        }
        return true;
    }
};

36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.


A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.


class Solution {
public:
    using BOA = vector<vector<char>>;

    bool ValidOrAdd(bitset<9> *n, const char val) {
        if (val != '.') {
            const int p = val - '1';
            if (n->test(p)) {
                return false;
            } else {
                n->set(p);
                return true;
            }
        }
        return true;
    }

    bool isValidSudoku(const BOA &b) {
        for (int i = 0; i < 9; i++) {
             bitset<9> n;
             for (int j = 0; j < 9; j++) {
                 if (!ValidOrAdd(&n, b[i][j])) {
                     return false;
                 }
             }
        }
        for (int j = 0; j < 9; j++) {
            bitset<9> n;
            for (int i = 0; i < 9; i++) {
                if (!ValidOrAdd(&n, b[i][j])) {
                    return false;
                }
            }
        }
        for (int i = 0; i < 9; i+=3) {
            for (int j = 0; j < 9; j+=3) {
                bitset<9> n;
                for (int k = i; k < i + 3; k++) {
                    for (int f = j; f < j + 3; f++) {
                        if (!ValidOrAdd(&n, b[k][f])) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
};

37. Sudoku Solver SNAPCHAT

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.


A sudoku puzzle...


...and its solution numbers marked in red.


class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
private:

    using BOA = vector<vector<char>>;
    using BIT = bitset<9>;
    struct POS {
        int r;
        int c;
        int cell() const {
            return (r/3) * 3 + (c/3);
        }
    };

    BIT row[10];
    BIT col[10];
    BIT cell[10];

    void change(BIT *val, int num, bool bitval) {
        if (bitval) {
            val->set(num);
        } else {
            val->reset(num);
        }
    }

    bool valid(const BOA &b, const POS &p, char val) {
        // Returns true if it is OK to put val in (r, c).
        const int test = val - '1';
        return !(row[p.r].test(test)) && !(col[p.c].test(test)) && !(cell[p.cell()].test(test));
    }

    void set(BOA &b, const POS &p, char val) {
        const int test = val - '1';
        b[p.r][p.c] = val;
        change(&row[p.r], test, true);
        change(&col[p.c], test, true);
        change(&cell[p.cell()], test, true);
    }

    void clear(BOA &b, const POS &p) {
        const int test = b[p.r][p.c] - '1';
        b[p.r][p.c] = '.';
        change(&row[p.r], test, false);
        change(&col[p.c], test, false);
        change(&cell[p.cell()], test, false);
    }

    bool helper(BOA &b, vector<POS> &candi) {
        if (candi.empty()) {
            return true;
        }
        const POS p = *candi.rbegin();
        candi.pop_back();
        for (char d = '1'; d <= '9'; d++) {
            if (valid(b, p, d)) {
                set(b, p, d);
                if (helper(b, candi)) return true;
                clear(b, p);
            }
        }
        candi.push_back(p);
        return false;
    }

    void sort(vector<POS> &candi) {
        std::sort(candi.begin(), candi.end(), [this](const POS &a, const POS &b) {
            int c_a = row[a.r].count() + col[a.c].count() + cell[a.cell()].count();
            int c_b = row[b.r].count() + col[b.c].count() + cell[b.cell()].count();
            return c_a < c_b;
        });
    }

    bool solve(BOA &board) {
        vector<POS> candi;
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                const POS p {r, c};
                if (board[p.r][p.c] != '.') {
                    set(board, p, board[p.r][p.c]);
                } else {
                    candi.push_back(p);
                }
            }
        }
        sort(candi);
        return helper(board, candi);
    }
};

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

class Solution {
public:
    using SET = unordered_set<string>;
    int ladderLength(string beg, string end, unordered_set<string>& w) {
        if (beg == end) {
            return 1;
        }
        SET left, right, *pleft, *pright;
        int dist = 2;
        left.insert(beg);
        right.insert(end);
        w.erase(beg);
        w.erase(end);

        while (!left.empty() && !right.empty()) {
            if (left.size() <= right.size()) {
                // We plan to process the one with smaller size first.
                // As it can be more balanced in that way.
                pleft = &left;
                pright = &right;
            } else {
                pleft = &right;
                pright = &left;
            }
            SET temp; // Store all neighbors of elements in pleft.
            for (string v : *pleft) {
                for (int i = 0; i < v.size(); ++i) {
                const char ori = v[i];
                for (char d = 'a'; d <= 'z'; ++d) {
                    v[i] = d;
                    if (pright->find(v) != pright->end()) {
                        return dist;
                    }
                    if (w.find(v) != w.end()) {
                        temp.insert(v);
                        w.erase(v);
                    }
                }
                v[i] = ori;
            }
            }
            swap(*pleft, temp);
            ++dist;
        }
        return 0;
    }
};

253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.


class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        if(intervals.size() == 0) {
            return 0;
        }
        map<int, int> map;
        // We have to use map here as the keys need to be sorted.
        // Thus the time complexity is O(nlogn).
        for(auto interval : intervals) {
            map[interval.start]++;
            map[interval.end]--;
        }
        int count = 0;
        int result = 0;
        for(auto it = map.begin() ; it != map.end() ; ++it) {
            count = count + it -> second;
            result = max(result, count);
        }
        return result;
    }
};

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x.start)
        rooms = []
        end_time_of_first_room = intervals[0].end
        heapq.heappush(rooms, end_time_of_first_room)
        for i in xrange(1, len(intervals), 1):
            start, end = intervals[i].start, intervals[i].end
            earliest_room_end_time = rooms[0]
            if start < earliest_room_end_time:
                heapq.heappush(rooms, end)
            else:
                heapq.heappushpop(rooms, end)
        return len(rooms)

/**
 * 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:
    int minMeetingRooms(vector<Interval>& intervals) {
        if (intervals.empty()) {
            return 0;
        }
        // Sort according to start time.
        sort(intervals.begin(), intervals.end(), [](const Interval &a, Interval &b) {
            return a.start < b.start;
        });
        // Top is min value, heap for the end times.
        priority_queue<int, vector<int>, greater<int>> end_times;
        end_times.push(intervals[0].end);
        for (int i = 1; i < intervals.size(); ++i) {
            const int end_t = intervals[i].end;
            const int start_t = intervals[i].start;
            if (start_t < end_times.top()) {
                // Need a new room, as the next start time is earlier than the earliest end time.
                end_times.push(end_t);
            } else {
                // One room is available for the next start meeting, use that room instead.
                end_times.pop();
                end_times.push(end_t);
            }
        }
        // The size of the queue is the largest room used.
        return end_times.size();
    }
};

206. Reverse Linked List

Reverse a singly linked list.


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *next = head->next;
        ListNode *new_head = reverseList(next);
        next->next = head;
        head->next = nullptr;
        return new_head;

    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *p = head;
        ListNode *q = head->next;
        ListNode *temp = nullptr;

        while (q) {
            temp = q->next;
            q->next = p;
            p = q;
            q = temp;
        }
        head->next = nullptr;
        return p;
    }
};

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; j++) {
                // put j as the root.
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
};

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

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

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) {
      stripSpace(s);
      reverse(s.begin(), s.end());
      int begin = 0, end = 0;
      while (begin < s.size()) {
        end = begin;
        while (end < s.size() && s[end] != ' ') {
          ++end;
        }
        reverse(s.begin() + begin, s.begin() + end);
        begin = end + 1;
      }
    }

    void stripSpace(string &s) {
      if (s.empty()) {
        return;
      }
      int p = 0;
      int w = 0;
      while (w < s.size() && s[w] == ' ') {
        ++w;
      }
      while (w < s.size()) {
        if (s[w] == ' ') {
          if (w + 1 < s.size() && s[w + 1] != ' ') {
            s[p++] = s[w++];
            continue;
          }
        } else {
          s[p++] = s[w++];
          continue;
        }
        ++w;
      }
      s.resize(p);
    }
};

403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

  • The number of stones is ≥ 2 and is < 1,100.
  • Each stone's position will be a non-negative integer < 231.
  • The first stone's position is always 0.

Example 1:

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping
1 unit to the 2nd stone, then 2 units to the 3rd stone, then
2 units to the 4th stone, then 3 units to the 6th stone,
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as
the gap between the 5th and 6th stone is too large.

class Solution {
public:
    using SET = unordered_set<int>;

    void updateJump(unordered_map<int, SET> &s, int unit, int k) {
        if (k > 0) {
            const int next_unit = unit + k;
            auto it = s.find(next_unit);
            if (it != s.end()) {
                it->second.insert(k);
            }
        }
    }

    bool canCross(vector<int>& stones) {
        if (stones.empty()) {
            return true;
        }
        // Stores all possible last-jumps for stone unit at a specific position.
        unordered_map<int, SET> stones_to_jump = {{0, {0}}};
        for (const int unit : stones) {
            if (unit > 0) {
                // Pre insert all stone unit into the map, this can
                // facilitate a little.
                stones_to_jump[unit] = {};
            }
        }
        // This points to all possible last-jumps for the last stone unit.
        auto final_iter = stones_to_jump.find(stones.back());
        for (const int unit : stones) {
            auto it = stones_to_jump.find(unit);
            if (it->second.empty()) {
                // If empty, then means no possible jumps to stone at <unit>
                continue;
            }
            for (const int jump : it->second) {
                // Update all other jumps starting from <unit>.
                updateJump(stones_to_jump, unit, jump - 1);
                updateJump(stones_to_jump, unit, jump);
                updateJump(stones_to_jump, unit, jump + 1);
            }
            if (!final_iter->second.empty()) {
                // This means we already find one solution, directly return.
                return true;
            }
        }
        return !final_iter->second.empty();
    }
};

270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ret_;
    int closestValue(TreeNode* root, double target) {
        if (root == nullptr) {
            return 0;
        }
        ret_ = root->val;
        return helper(root, target, abs(target - root->val));
    }

    int helper(TreeNode *root, double target, double dis) {
        if (root == nullptr) {
            return ret_;
        }
        const double new_dis = abs(target - root->val);
        if (new_dis < dis) {
            ret_ = root->val;
        }
        dis = min(new_dis, dis);
        if (target < root->val) {
            return helper(root->left, target, dis);
        } else {
            return helper(root->right, target, dis);
        }
    }
};

402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

class Solution {
public:
    string removeKdigits(string num, const int k) {
        if (num.size() <= k) {
            return "0";
        }
        if (num == "0") {
            return num;
        }
        string res;
        // We always choose to pop out the largest value in the stack.
        int deleted = 0;
        for (int i = 0; i < num.size(); ++i) {
            if (res.empty() && num[i] == '0') {
                // Lead value cannot be 0. So skip to the next value.
                continue;
            }
            if (deleted == k || res.empty() || num[i] >= res.back()) {
                // 3 conditions:
                //   1, We have deleted enough value, so simply insert all remains.
                //   2, No available value right now, in this case num[i] != '0'
                //      by default so insert it.
                //   3, The next value is larger, so insert it as it should
                //      have a higher priority to delete the the current
                //       top one in stack.
                res.push_back(num[i]);
                continue;
            }
            // Pop all previous string out.
            // We meet a value smaller than the current stack top,
            // so delete the current stack top.
            res.pop_back();
            --i;
            ++deleted;
        }
        // res: first element is not 0, but its length maybe longer or shorter
        //      as deleted may not equal to k.
        res = res.substr(0, num.size() - k);
        return res.empty() ? "0" : res;
    }
};

289. Game of Life

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up:

  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.


class Solution {
public:
    using BOA = vector<vector<int>>;
    int numlive(const BOA &b, const int i, const int j) {
        int res;
        for (int k = max(0, i - 1); k <= i + 1 && k < b.size(); ++k) {
            for (int f = max(0, j - 1); f <= j + 1 && f < b[0].size(); ++f) {
                if (k != i || f != j) {
                    res += (b[k][f] & 1);
                }
            }
        }
        return res;
    }

    void gameOfLife(BOA& b) {
        if (b.empty() || b[0].empty()) {
            return;
        }
        const int m = b.size();
        const int n = b[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                const int num_live = numlive(b, i, j);
                const bool is_live = (b[i][j] & 1);
                // cout << is_live << " " << num_live << " " << i << " " << j << endl;
                if (is_live) {
                    if (num_live < 2 || num_live > 3) {
                        // Die
                    } else {
                        // Live
                        b[i][j] |= 2;
                    }
                } else {
                    if (num_live == 3) {
                        b[i][j] |= 2;
                    }
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                b[i][j] = (b[i][j] >> 1) & 1;
            }
        }
    }
};

439. Ternary Expression Parser

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

  1. The length of the given string is ≤ 10000.
  2. Each number will contain only one digit.
  3. The conditional expressions group right-to-left (as usual in most languages).
  4. The condition will always be either T or F. That is, the condition will never be a digit.
  5. The result of the expression will always evaluate to either a digit 0-9, T or F.

Example 1:

Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"

Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

class Solution {
public:
    string parseTernary(string e) {
        if (e.empty()) {
            return "";
        }
        if (e.size() == 1) {
            return e;
        }
        if (e[1] == ':') {
            return e.substr(0, 1);
        }
        if (e[0] == 'T') {
            return parseTernary(e.substr(2));
        } else if (e[0] == 'F') {
            int mat = 1;
            int i = 2;
            for (; i < e.size(); ++i) {
                if (e[i] == '?') {
                    ++mat;
                } else if (e[i] == ':') {
                    --mat;
                }
                if (mat == 0) break;
            }
            return parseTernary(e.substr(i + 1));
        } else {
            return e.substr(0, 1);
        }
    }
};