2024 March 30 Problems
60 views
Skip to first unread message
daryl...@gmail.com
Mar 30, 2024, 12:36:28 PMMar 30
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.
Join Zoom Meeting
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.
Hard problem has been rolled over from last week for the last time. We'll go over the official solution if no one is able to solve it.
3083Existence of a Substring in a String and Its Reverse65.8%Easy
3076Shortest Uncommon Substring in an Array44.6%Medium
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
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Andriy T
Mar 30, 2024, 1:31:12 PMMar 30
to leetcode-meetup
HashSet based bruteforce
Time O(n) Space O(n)
class Solution {
public boolean isSubstringPresent(String s) {
Set<String> set = new HashSet<>();
for (int i = 0;i<s.length();i++) {
if (i+1 < s.length()) {
String ss = "" + s.charAt(i);
ss += s.charAt(i+1);
set.add(ss);
}
}
for (int i = s.length()-1;i>=0;i--) {
if (i-1 >= 0) {
String ss = "" + s.charAt(i);
ss += s.charAt(i-1);
if (set.contains(ss)) {
return true;
}
}
}
return false;
}
}
Flocela Maldonado
Mar 30, 2024, 2:03:45 PMMar 30
to leetcode-meetup
Time: n*l, where n is the number of words, and l is the length of the words. Memory: O(n*l)
class Solution {
public:
vector<string> shortestSubstrings(vector<string>& arr) {
vector<string> shortestSubstrings(arr.size(), "");
unordered_map<string, int> countPerSubstring{};
// for each word in arr
for(int ii=0; ii<arr.size(); ++ii)
{
// for each word in arr make an unordered_set of all the substrings
unordered_set<string> subStringsForii{};
for(int jj=0; jj<arr[ii].size(); ++jj)
{
// all substrings that start with arr[ii][kk]
// append substring with arr[ii][jj] as jj moves to the right.
string base = "";
for(int kk=jj; kk<arr[ii].size(); ++kk)
{
base += arr[ii][kk];
subStringsForii.insert(base);
}
}
// add each substring that was found in arr[ii] to the map of countPerSubstring
for(const string& s : subStringsForii)
{
++countPerSubstring[s];
}
}
for(int ii=0; ii<arr.size(); ++ii)
{
string shortestForWordAtii = "";
for(int jj=0; jj<arr[ii].size(); ++jj)
{
string base = "";
for(int kk=jj; kk<arr[ii].size(); ++kk)
{
base += arr[ii][kk];
if(countPerSubstring[base]== 1)
{
if(shortestForWordAtii == "")
{
shortestForWordAtii = base;
}
else if(base.size() < shortestForWordAtii.size())
{
shortestForWordAtii = base;
}
else if(base.size() == shortestForWordAtii.size() && base < shortestForWordAtii)
{
shortestForWordAtii = base;
}
}
}
}
shortestSubstrings[ii] = shortestForWordAtii;
}
return shortestSubstrings;
}
};
Flocela Maldonado
Mar 30, 2024, 4:44:28 PMMar 30
to leetcode-meetup
April 6th: First Meeting of the Month! Peet's Coffee after the meeting!!!
Vivek H
Apr 5, 2024, 1:04:06 AMApr 5
to leetcod...@googlegroups.com
*********************************************************************************************
*********************************************************************************************
class Solution {
public:
static bool comp(string &a, string &b) {
if(a.length() == b.length())
return a < b;
return a.length() < b.length();
}
vector<string> shortestSubstrings(vector<string>& arr) {
/* map<substring, index in arr> M */
map<string, vector<int>> M;
//create a map of all shortestSubstrings
for(int i=0; i<arr.size(); i++) {
for(int j=0; j<arr[i].size(); j++) {
for(int k=j; k<arr[i].size(); k++) {
string subStr = arr[i].substr(j, k-j+1);
if(M.count(subStr) != 0 && M[subStr].back() == i)
continue;
M[subStr].push_back(i);
}
}
}
map<int, vector<string>> idxStrMap;
for(auto &a : M) {
/*cout << a.first << ": ";
for(auto &b : a.second) {
cout << b << " ";
}
cout << endl;*/
if(a.second.size() == 1) {
idxStrMap[a.second[0]].push_back(a.first);
vector<string> V = idxStrMap[a.second[0]];
if(V.size() > 0) {
sort(V.begin(), V.end(), comp);
}
idxStrMap[a.second[0]] = V;
}
}
vector<string> result;
for(int i=0; i<arr.size(); i++) {
if(idxStrMap.count(i) == 0) {
result.push_back("");
} else {
result.push_back(idxStrMap[i][0]);
}
}
return result;
}
};
--
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/6f38840a-b9e1-4c46-85d5-f7a4881884bbn%40googlegroups.com.
Vivek H
Apr 5, 2024, 1:11:01 AMApr 5
to leetcod...@googlegroups.com
***********************************************************************************
***********************************************************************************
class Solution {
public:
bool isSubstringPresent(string s) {
if (s.length() == 1)
return false;
set<string> S;
for (int i = 1; i < s.length(); i++) {
string str = string(1, s[i-1]) + string(1, s[i]);
//cout << str << endl;
S.insert(str);
}
reverse(s.begin(), s.end());
for (int i = 1; i < s.length(); i++) {
string str = string(1, s[i-1]) + string(1, s[i]);
if (S.find(str) != S.end())
return true;
}
return false;
}
};
--
Reply all
Reply to author
Forward
0 new messages