Daily Coding Challenge #49

Daily Coding Challenge (87 Part Series)

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

/*
LeetCode - Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input:
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.
*/

class Solution {
public:
struct TrieNode {
TrieNode* children[26];
string word;
TrieNode():word(""){
for(int i=0;i<26;i++) {
children[i] = nullptr;
}
}
};

TrieNode* buildTrie(vector<string>& words){
TrieNode* root = new TrieNode();
for(string word:words){
TrieNode *cur = root;
for(char c:word){
if(cur->children[c-'a']==nullptr){
cur->children[c-'a']=new TrieNode();
}
cur = cur->children[c-'a'];
}
cur->word = word;
}
return root;
}

void dfs(int i, int j, vector<vector<char>>& board, TrieNode* root, vector<string>& ans){
char c=board[i][j];
// if visited or no such character, return
if(c=='*'||!root->children[c-'a']) return;
root = root->children[c-'a'];
if(root->word.size()){
ans.push_back(root->word);
// de-duplicate from trie node
root->word="";
}
// set it to other character. consider it has been visited
board[i][j]='*';
// dfs - 4 directions
if(i>0) dfs(i-1,j,board,root,ans);
if(j>0) dfs(i,j-1,board,root,ans);
if(i<board.size()-1) dfs(i+1,j,board,root,ans);
if(j<board[0].size()-1) dfs(i,j+1,board,root,ans);
// backtracking
board[i][j]=c;
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
// approach: trie + dfs + backtracking
// build trie node
TrieNode* root = buildTrie(words);
vector<string> ans;
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
// dfs
dfs(i,j,board,root,ans);
}
}
return ans;
}
};

/*
LeetCode - Check If Array Pairs Are Divisible by k

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return True If you can find a way to do that or False otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).
Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).
Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.
Example 4:

Input: arr = [-10,10], k = 2
Output: true
Example 5:

Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true

Constraints:

arr.length == n
1 <= n <= 10^5
n is even.
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5
*/

class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
unordered_map<int,int> m;
for(int x:arr) {
// m[(x%k)]++;  // this line only works for non-negative values
m[(x%k+k)%k]++; // for negative values, you need to tune it back to a possible value using (x%k+k)%k
// or m[x%k<0?(x%k)+k:(x%k)]++;
}
// return false if we can't make m[0] a pair
if(m[0]%2==1) return false;
for(int i=1;i<k;i++){
// same for others. find the corresponding pair.
if(m[i]!=m[k-i]){
return false;
}
}
return true;
}
};

class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
// weak test case. still pass with below solution.
// this case should return false instead of true
// [1,1,1,1,1,1]
// 6
long long ans=0;
for(int x:arr) ans+=x;
return (ans%k==0);
}
};

The source code is available in corresponding repo below. Star and watch for timely updates!

wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Daily Coding Challenge (87 Part Series)

Posted on by:

Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.