0211-0220

211. Add and Search Word - Data structure design $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class WordDictionary {
 public:
  void addWord(string word) {
    TrieNode* node = &root;
    for (char c : word) {
      TrieNode*& next = node->children[c - 'a'];
      if (!next) next = new TrieNode;
      node = next;
    }
    node->isWord = true;
  }

  bool search(string word) { return dfs(word, 0, &root); }

 private:
  struct TrieNode {
    TrieNode() : children(26), isWord(false) {}
    ~TrieNode() {
      for (TrieNode* child : children) delete child;
    }

    vector<TrieNode*> children;
    bool isWord;
  };

  TrieNode root;

  bool dfs(const string& word, int depth, TrieNode* node) {
    if (depth == word.length()) return node->isWord;
    if (word[depth] != '.') {
      TrieNode* next = node->children[word[depth] - 'a'];
      return next ? dfs(word, depth + 1, next) : false;
    }

    for (int i = 0; i < 26; ++i)
      if (node->children[i] && dfs(word, depth + 1, node->children[i]))
        return true;

    return false;
  }
};

212. Word Search II $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
 public:
  vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    for (const string& word : words) insert(word);

    vector<string> ans;

    for (int i = 0; i < board.size(); ++i)
      for (int j = 0; j < board[0].size(); ++j) dfs(board, i, j, &root, ans);

    return ans;
  }

 private:
  struct TrieNode {
    TrieNode() : children(26), word(nullptr) {}
    ~TrieNode() {
      for (TrieNode* child : children) delete (child);
    }

    vector<TrieNode*> children;
    const string* word;
  };

  TrieNode root;

  void insert(const string& word) {
    TrieNode* node = &root;
    for (char c : word) {
      TrieNode*& next = node->children[c - 'a'];
      if (!next) next = new TrieNode;
      node = next;
    }
    node->word = &word;
  }

  void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node,
           vector<string>& ans) {
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
        board[i][j] == '*')
      return;

    char c = board[i][j];
    TrieNode* next = node->children[c - 'a'];
    if (!next) return;
    if (next->word) {
      ans.push_back(*next->word);
      next->word = nullptr;
    }

    board[i][j] = '*';
    dfs(board, i + 1, j, next, ans);
    dfs(board, i - 1, j, next, ans);
    dfs(board, i, j + 1, next, ans);
    dfs(board, i, j - 1, next, ans);
    board[i][j] = c;
  }
};

213. House Robber II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int rob(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() < 2) return nums[0];

    const int n = nums.size();

    return max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
  }

 private:
  int rob(vector<int>& nums, int l, int r) {
    int dp1 = 0;
    int dp2 = 0;

    for (int i = l; i <= r; ++i) {
      int temp = dp1;
      dp1 = max(dp1, dp2 + nums[i]);
      dp2 = temp;
    }

    return dp1;
  }
};

214. Shortest Palindrome $\star\star\star$

215. Kth Largest Element in an Array $\star\star$

1
2
3
4
5
6
7
8
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), greater<int>());

    return nums[k - 1];
  }
};

216. Combination Sum III $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> ans;
    vector<int> path;

    dfs(k, n, 1, path, ans);

    return ans;
  }

 private:
  void dfs(int k, int n, int s, vector<int>& path, vector<vector<int>>& ans) {
    if (k == 0 && n == 0) {
      ans.push_back(path);
      return;
    }
    if (k == 0 || n < 0) return;

    for (int i = s; i <= 9; ++i) {
      path.push_back(i);
      dfs(k - 1, n - i, i + 1, path, ans);
      path.pop_back();
    }
  }
};

217. Contains Duplicate $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> set;

    for (int num : nums) {
      if (set.count(num)) return true;
      set.insert(num);
    }

    return false;
  }
};

218. The Skyline Problem $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<vector<int>> ans;
    vector<vector<int>> events;

    for (vector<int>& building : buildings) {
      events.push_back({building[0], building[2]});
      events.push_back({building[1], -building[2]});
    }

    sort(events.begin(), events.end(),
         [](const vector<int>& e1, const vector<int>& e2) {
           return e1[0] == e2[0] ? e1[1] > e2[1] : e1[0] < e2[0];
         });

    for (vector<int>& event : events) {
      int x = event[0];
      int h = abs(event[1]);

      if (event[1] > 0) {
        if (h > maxHeight()) ans.push_back({x, h});
        set.insert(h);
      } else {
        set.erase(set.equal_range(h).first);
        if (h > maxHeight()) ans.push_back({x, maxHeight()});
      }
    }

    return ans;
  }

 private:
  multiset<int> set;
  int maxHeight() const { return set.empty() ? 0 : *set.rbegin(); }
};

219. Contains Duplicate II $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_set<int> set;

    for (int i = 0; i < nums.size(); ++i) {
      if (i > k) set.erase(nums[i - k - 1]);
      if (set.count(nums[i])) return true;
      set.insert(nums[i]);
    }

    return false;
  }
};

220. Contains Duplicate III $\star\star$