Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each test
Word Search II LeetCode Solution
Links
Question
Given an m x n
board
of characters and a list of strings words
, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example 1:
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"]
Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j]
is a lowercase English letter.1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i]
consists of lowercase English letters.- All the strings of
words
are unique.
Explanation
This problem is difficult to understand at first go for a newbie coder since this to solve this question you need to know about DFS(Depth First Search) and Backtracking. We first create a trie data structure with words. Each node stores a reference count, this is used since we already have got all words for a node so we should not use it again. Now for every frid we do the depth first search taking head of trie. Every time we move to a neighbor we mark the current node as visited and the neighbor extracts its relevant information from trie. If we found the leaf node we decrement that word from trie. That's all and now you need to code it properly.
Below the solution is given in Java, C++, Python. I recommend give it a try then see the solutions.
More information about LeetCode Daily Challenge
More Information About LeetCode Daily Challenge
LeetCode is a great coding platform which provides daily problems to solve and maintain a streak of coding. This platform helps in improvement of coding skills and attempting the daily challenge makes our practice of coding regular. With its bunch of questions available it is one of the best coding platforms where you can have self improvement. LeetCode also holds weekly and biweekly contests which is a great place to implement you knowledge and coding skills which you learnt through out the week by performing the daily challenge. It also provides badges if a coder solves all the daily problems of a month. For some lucky winners T-shirts are also given and that too for free. If you get the pro version you can get more from LeetCode like questions that are asked in interviews, detailed explanation of each chapter and each concept and much more. LeetCode challenges participants with a problem from our carefully curated collection of interview problems every 24 hours.
All users with all levels of coding background are welcome to join!
@PREMIUM USERS will have an extra carefully curated premium challenge weekly and earn extra LeetCoin rewards. The premium challenge will be available together with the first October challenge of the week and closed together with the November challenge of the week.
Starting from 2021, users who completed all Daily LeetCoding Challenge non-premium problems for the month (with or without using Time Travel Tickets) will win a badge to recognize their consistency! Your badges will be displayed on your profile page. Completing each non-premium daily challenge. (+10 LeetCoins)
Completing 25 to 30 non-premium daily challenges without using Time Travel Ticket will be eligible for an additional 25 LeetCoins. (Total = 275 to 325 LeetCoins)
Completing all 31 non-premium daily challenges without using Time Travel Ticket will be eligible for an additional 50 LeetCoins, plus a chance to win a secret prize ( Total = 385 LeetCoins + *Lucky Draw)!
Lucky Draw: Those who complete all 31 non-premium daily challenges will be automatically entered into a Lucky Draw, where LeetCode staff will randomly select 3 lucky participants to each receive one LeetCode Polo Shirt on top of their rewards! Do you have experience trying to keep a streak but failed because you missed one of the challenges?
Hoping you can travel back to the missed deadline to complete the challenge but that's not possible......or is it?
With the new Time Travel Ticket , it's possible! In order to time travel, you will need to redeem a Time Travel Ticket with your LeetCoins. You can redeem up to 3 tickets per month and the tickets are only usable through the end of the month in which they are redeemed but you can use the tickets to make up any invalid or late submission of the current year. To join, just start solving the daily problem on the calendar of the problem page. You can also find the daily problem listed on the top of the problem page. No registration is required. The daily problem will be updated on every 12 a.m. Coordinated Universal Time (UTC) and you will have 24 hours to solve that challenge. Thar's all you needed to know about Daily LeetCode Challenge.
Program Code
Java
public List<String> findWords(char[][] board, String[] words) {
int M = board.length, N = board[0].length;
List<String> possibleWords = new ArrayList<>();
int[] countChar = new int[26];
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
countChar[board[i][j] - 'a']++;
}
}
for(String word: words) {
boolean valid = true;
for(char ch: word.toCharArray()) {
if(countChar[ch - 'a'] == 0) {
valid = false;
break;
}
}
if(valid) possibleWords.add(word);
}
if(possibleWords.size() == 0)
return new ArrayList<>();
List<String> result = new ArrayList<>();
for(String word: possibleWords) {
for(int i = 0; i < M; i++) {
boolean found = false;
for(int j = 0; j < N; j++) {
if(word.charAt(0) == board[i][j]) {
if(dfs(board, word, i, j, 0)) {
found = true;
result.add(word);
break;
}
}
}
if(found) break;
}
}
return result;
}
boolean dfs(char[][] board, String word, int i, int j, int pos) {
if(pos == word.length())
return true;
int M = board.length, N = board[0].length;
if(i < 0 || i >= M || j < 0 || j >= N || board[i][j] == '*' || board[i][j] != word.charAt(pos))
return false;
char prevValue = board[i][j];
board[i][j] = '*';
boolean result = dfs(board, word, i + 1, j, pos + 1) ||
dfs(board, word, i - 1, j, pos + 1) ||
dfs(board, word, i, j + 1, pos + 1) ||
dfs(board, word, i, j - 1, pos + 1);
board[i][j] = prevValue;
return result;
}
C++
class Solution {
public:
struct Node{
bool eow;
Node* nb[26];
Node(){eow = false; for(int i=0;i!=26;i++) nb[i] = NULL;}
};
int y, x, yend, xend;
Node *root;
vector<string> answer;
void delete_word(string &s){
Node *tmp = root;
vector<Node*> nodes;
for(int i = 0 ; i != s.size(); i++) {
nodes.push_back(tmp);
tmp = tmp->nb[s[i] - 'a'];
}
tmp->eow = false;
for(int i = s.size() - 1; i >= 0 ; i--){
if(nodes[i]->nb[s[i] - 'a']->eow) break;
bool flag = false;
for(int j = 0; j != 26; j++)
if(nodes[i]->nb[j]) {flag = true; break;}
if(flag) break;
nodes[i]->nb[s[i] - 'a'] = NULL;
}
}
void construct_answer(vector<pair<int,int>> &pos, vector<vector<char>>& board){
string tmp = "";
for(auto i : pos) tmp.push_back(board[i.first][i.second]);
answer.push_back(tmp);
}
void helper(vector<vector<char>>& board, int i, int j, vector<vector<char>> &visited){
static stack <tuple<int,int, Node*,int>> st;
static vector<pair<int,int>> pos;
st.push({i,j,root,0});
while(!st.empty()){
auto[ yy ,xx , tmp, len] = st.top();st.pop();
int idx = board[yy][xx]-'a';
if(tmp->nb[idx]){
while(len != pos.size()){
visited[pos.back().first][pos.back().second] = 0;
pos.pop_back();
}
if(visited[yy][xx]) continue;
visited[yy][xx] = 1;
pos.push_back({yy,xx});
if(tmp->nb[idx]->eow) {construct_answer(pos, board);delete_word(answer.back());}
}
else continue;
if(yy && !visited[yy-1][xx]) st.push({yy-1,xx,tmp->nb[idx], len + 1});
if(yy != yend && !visited[yy+1][xx]) st.push({yy+1,xx,tmp->nb[idx], len + 1});
if(xx && !visited[yy][xx-1]) st.push({yy,xx-1,tmp->nb[idx], len + 1});
if(xx != xend && !visited[yy][xx+1] ) st.push({yy,xx+1,tmp->nb[idx], len + 1});
}
for(int w = 0; w < pos.size(); w++){
visited[pos[w].first][pos[w].second] = 0;
}
pos.clear();
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
root = new Node();
y = board.size(), x = board[0].size();
vector<vector<char>> visited(y, vector<char>(x,0));
yend = y - 1, xend = x - 1;
int limit = y*x;
for(auto word : words){
if(word.size() > limit) continue;
Node *tmp = root;
for(int j = 0;j < word.size(); j++){
int idx = word[j] - 'a';
if(tmp->nb[idx]) tmp = tmp->nb[idx];
else
for(;j != word.size();j++){
idx = word[j] - 'a';
tmp->nb[idx] = new Node();
tmp = tmp->nb[idx];
}
}
tmp->eow = true;
}
for(int i = 0; i != y; i++)
for(int j = 0; j != x; j++)
helper(board, i, j, visited);
return answer;
}
};
Python
class TrieNode:
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for w in word:
node = node.children[w]
node.isWord = True
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m = len(board)
n = len(board[0])
res = []
trie = Trie()
root = trie.root
for w in words:
trie.insert(w)
dirs = {(0, 1), (1, 0), (0, -1), (-1, 0)}
def dfs(board, node, x, y, path, res):
if node.isWord:
res.append(path)
# Unset the node isWord to False to avoid overlapped prefixes. Like 'oa' and 'oaa'
node.isWord = False
# Using dfs to search the Trie. We can garentee the x y here is not out of index
tmp = board[x][y]
node = node.children.get(tmp)
if not node:
return
# Set the current cell to # which marks the cell as visited
board[x][y] = "#"
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and board[nx][ny] != "#":
dfs(board, node, nx, ny, path + tmp, res)
# Unset the current cell to enable further searches.
board[x][y] = tmp
# This condition is critical to deal with the corner case, if the board is [["a"]] and the word itself is also ["a"]. Our DFS solution will miss this corner case as the for loop will not be entered and the node.isWord will not be checked. So we have to check it again here.
if node.isWord:
res.append(path + tmp)
node.isWord = False
for i in range(m):
for j in range(n):
dfs(board, root, i, j, "", res)
return res
Comments
Post a Comment