2024 May 11 Problems
52 views
Skip to first unread message
daryl...@gmail.com
May 11, 2024, 12:43:40 PMMay 11
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.
1030Matrix Cells in Distance Order71.0%Easy
1048Longest String Chain61.0%Medium
1074Number of Submatrices That Sum to Target74.4%Hard
Join Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Please post your solutions to this thread so others can use this as a reference.
1030Matrix Cells in Distance Order71.0%Easy
1048Longest String Chain61.0%Medium
1074Number of Submatrices That Sum to Target74.4%Hard
Please download and import the following iCalendar (.ics) files to your calendar system.
Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZJoin Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Flocela Maldonado
May 11, 2024, 1:18:24 PMMay 11
to leetcode-meetup
Time: O(n*log(n)), Memory: O(n), where n is rows * cols
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
vector<vector<int>> cells(rows*cols, vector<int>(2));
for(int rr=0; rr<rows; ++rr)
{
for(int cc=0; cc<cols; ++cc)
{
cells[rr*cols + cc][0] = rr;
cells[rr*cols + cc][1] = cc;
}
}
sort(
cells.begin(),
cells.end(),
[rCenter, cCenter](const vector<int>& a, const vector<int>& b)
{
return
(std::abs(a[0] - rCenter) + std::abs(a[1] - cCenter)) <
(std::abs(b[0] - rCenter) + std::abs(b[1] - cCenter));
});
return cells;
}
};
Flocela Maldonado
May 11, 2024, 8:18:29 PMMay 11
to leetcode-meetup
1048Longest String Chain61.0%Medium
Looking at hint 2. Time: O(n^2), Memory O(n)
Looking at hint 2. Time: O(n^2), Memory O(n)
class Solution {
public:
// Iterate through tree, where every node is a word. And every node's children are the set of predecessors associated with that word.
int dfsGetHeight(const string& word, unordered_map<string, unordered_set<string>>& setOfPredecessorsPerWord)
{
int maxH = 0;
for(const string& successor : setOfPredecessorsPerWord[word])
{
int height = dfsGetHeight(successor, setOfPredecessorsPerWord);
maxH = std::max(maxH, height);
}
return maxH + 1;
}
int longestStrChain(vector<string>& words) {
// Group the words by their length.
unordered_map<int, unordered_set<string>> wordsPerLength{};
for(const string& word : words)
{
if(wordsPerLength.find(word.size()) == wordsPerLength.end())
{
wordsPerLength.insert({word.size(), unordered_set<string>{}});
}
wordsPerLength[word.size()].insert(word);
}
// Every unique word has a set of predecessors (could be the empty set).
unordered_map<string, unordered_set<string>> setOfPredecessorsPerWord{};
for(const string& word : words)
{
if(setOfPredecessorsPerWord.find(word) == setOfPredecessorsPerWord.end())
{
setOfPredecessorsPerWord.insert({word, unordered_set<string>{}});
}
}
unordered_set<string> wordIsSeen{};
// Add predecessors to each word's predecessorSet.
for(const string& word : words)
{
// Don't do the same word twice. Already found the predecessors for this word.
if(wordIsSeen.find(word) != wordIsSeen.end())
{
continue;
}
wordIsSeen.insert(word);
// If there are no words with a length of one smaller than the word, then continue to next word.
if(wordsPerLength.find(word.size()-1) == wordsPerLength.end())
{
continue;
}
// Check every word with the correct length (that's word.size()-1) to see if it's a predecessor.
for(string shortWord : wordsPerLength[word.size()-1])
{
// short word's index
int s_ii = 0;
// w_ii is the word's index
int w_ii = 0;
while(w_ii < word.size() && s_ii < shortWord.size())
{
// if the letter's don't match, skip this letter in word.
if(word[w_ii] != shortWord[s_ii])
{
++w_ii;
}
else
{
++s_ii;
++w_ii;
}
// if already skipped more than 1 letter, then it's not a predecessor, break.
if ( (w_ii-s_ii) > 1)
{
break;
}
}
// It's a predecessor if zero or more letters were skipped.
if (w_ii-s_ii <= 1)
{
setOfPredecessorsPerWord[word].insert(shortWord);
}
}
}
vector<int> wordLengths{};
for(auto& lengthAndWords : wordsPerLength)
{
wordLengths.push_back(lengthAndWords.first);
}
sort(wordLengths.begin(), wordLengths.end(), [](const int& a, const int& b){ return b < a;});
// length of longest word chain
int maxWC = 0;
// Go through each word, but do the long words first (using sorted wordLengths).
for(int length : wordLengths)
{
// if the length of these words are smaller than the longest word chain, then there's no chance that the word will make a longer word chain than maxWC.
// The longest word chain a word can make is it's length.
if(length < maxWC)
{
break;
}
for(auto& word : wordsPerLength[length])
{
int height = dfsGetHeight(word, setOfPredecessorsPerWord);
maxWC = std::max(maxWC, height);
}
}
return maxWC;
}
};
Vivek H
May 17, 2024, 8:46:38 PMMay 17
to leetcod...@googlegroups.com
***********************************************************
***********************************************************
1. visulaze the data as graph, there is an edge from string X to string Y, if X is predecessor of Y
2. run bfs on graph to find the longest chain
complexity = O(Vertices + edges)
class Solution {
public:
static bool comp(string& word1, string& word2) {
return word1.length() < word2.length();
}
bool isPredecessor(string& word1, string& word2) {
int len1 = word1.length();
int len2 = word2.length();
if(abs(len1-len2) != 1)
return false;
/* keep remove one char at a time from the bigger string and
compare with the smaller one */
for(int i=0; i<len2; i++) {
string str = word2;
str.erase(i, 1);
if(str == word1)
return true;
}
return false;
}
int bfs(map<string, vector<string>>& G, string node) {
queue<pair<string, int>> Q;
map<string, bool> visited;
visited[node] = true;
Q.push({node, 1});
int length = 1;
while(!Q.empty()) {
string front = Q.front().first;
int len = Q.front().second;
length = max(length, len);
//cout << "len=" << length << endl;
Q.pop();
//get the neigbors
for(int i=0; i<G[front].size(); i++) {
if(visited.count(G[front][i]) == 0) {
//not visited, push into Q and mark as visited
visited[G[front][i]] = true;
Q.push({G[front][i], len+1});
//cout << len+1 << endl;
}
}
}
return length;
}
int longestStrChain(vector<string>& words) {
sort(words.begin(), words.end(), comp);
map<string, vector<string>> G;
for(int i=0; i<words.size(); i++) {
G[words[i]] = {};
}
for(int i=0; i<words.size()-1; i++) {
for(int j=i+1; j<words.size(); j++) {
if(isPredecessor(words[i], words[j])) {
G[words[i]].push_back(words[j]);
}
}
}
int longestChain = -1;
for(auto &a : G) {
longestChain = max(longestChain, bfs(G, a.first));
}
return longestChain;
}
};
--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/47889732-2c5e-4ab1-a432-999267154355n%40googlegroups.com.
Vivek H
May 17, 2024, 9:12:58 PMMay 17
to leetcod...@googlegroups.com
*************************************************************************
*************************************************************************
class Solution {
public:
struct comp {
bool operator()(const pair<pair<int, int>, int>& p1, const pair<pair<int, int>, int>& p2) const{
return p1.second <= p2.second;
}
};
vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
set<pair<pair<int, int>, int>, comp> S;
for(int i=0; i<rows; i++) {
for(int j=0; j<cols; j++) {
int dist = abs(i-rCenter) + abs(j-cCenter);
//cout << "{" << i << "," << j << "} " << dist << endl;
S.insert({{i,j}, dist});
}
}
vector<vector<int>> result;
for(auto &a : S) {
result.push_back({a.first.first, a.first.second});
}
return result;
}
};
--
Reply all
Reply to author
Forward
0 new messages