2020 June 27 Problems

Daryl Wang

unread,

Jun 27, 2020, 12:12:39 PM6/27/20

to leetcode-meetup

Please work on the problems at home and post your solutions to the thread. I will be discussing the answers on July 4th morning.

824

Goat Latin

63.0%

Easy

890

Find and Replace Pattern

73.2%

Medium

899

Orderly Queue

51.5%

Hard

Tarini Pattanaik

unread,

Jun 27, 2020, 1:50:46 PM6/27/20

to leetcod...@googlegroups.com

824. Goat Latin

Runtime: 6 ms, faster than 41.10% of Java online submissions for Goat Latin.

public String toGoatLatin(String S) {
Set<Character> set = new HashSet<Character>();
set.add('a');
set.add('e');
set.add('i');
set.add('o');
set.add('u');
set.add('A');
set.add('E');
set.add('I');
set.add('O');
set.add('U');

String[] words = S.split(" ");
StringBuilder sb = new StringBuilder();

int i = 0;
for (String word: words ) {
if (set.contains(word.charAt(0))) {
sb.append(word);

} else {
String tmp = word.substring(1);
tmp = tmp + word.charAt(0);
sb.append(tmp);
}

sb.append("ma");

for (int j = 1; j <= i+1; j++)
sb.append("a");

if (i != words.length -1)
sb.append(" ");
i++;
}

return sb.toString();
}

--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS

https://www.techbayarea.us/

FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
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/a1950de3-c188-4fc6-90ed-022c740754e5o%40googlegroups.com.

rajat aggarwal

unread,

Jun 27, 2020, 5:31:51 PM6/27/20

to leetcod...@googlegroups.com

824

Goat Latin

63.0%

Easy

public String toGoatLatin(String S) {

// Split the string into string Array

String[] arr=S.split(" ");

StringBuilder result = new StringBuilder();

for(int i=0; i< arr.length; i++)
{

if(!checkVowel(arr[i].charAt(0)))
{
result.append(arr[i].substring(1,arr[i].length()));
result.append(arr[i].charAt(0));
}
else
{
result.append(arr[i]);
}

result.append("ma");
result.append(addA(i+1)).append(" ");

}

return result.toString().trim();

}

private boolean checkVowel(char ch)
{
char ch1=Character.toUpperCase(ch);
if(ch1 == 'A' || ch1== 'E' || ch1=='I' || ch1=='O' || ch1=='U' )
{
return true;
}

return false;
}

private String addA(int count)
{
StringBuilder sb=new StringBuilder();
for(int i=0; i< count; i++)
{
sb.append('a');
}

return sb.toString();
}

On Sat, Jun 27, 2020 at 9:12 AM Daryl Wang <daryl...@gmail.com> wrote:

--

rajat aggarwal

unread,

Jun 27, 2020, 6:23:17 PM6/27/20

to leetcod...@googlegroups.com

890

Find and Replace Pattern

73.2%

Mediu

public List<String> findAndReplacePattern(String[] words, String pattern) {

List<String> result=new ArrayList<>();

for(int i=0; i< words.length; i++)
{

if(words[i].length() != pattern.length())
{
continue;
}

// go over both words if length match

HashMap<Character, Character> map=new HashMap<>();
HashMap<Character, Character> reversemap=new HashMap<>();

boolean match=true;

for(int j=0; j< pattern.length(); j++)
{

if(map.containsKey(pattern.charAt(j)) || reversemap.containsKey(words[i].charAt(j)))
{
boolean b1=true;
boolean b2=true;
if(map.containsKey(pattern.charAt(j)))
{
char ch=(char) map.get(pattern.charAt(j));
if( ch != words[i].charAt(j))
{
b1=false;
}

}

if( reversemap.containsKey(words[i].charAt(j)))
{
char ch=(char) reversemap.get(words[i].charAt(j));
if( ch != pattern.charAt(j))
{
b2=false;
}
}

if(!( b1 && b2))
{
match=false;
break;
}

}
else
{
map.put(pattern.charAt(j), words[i].charAt(j));
reversemap.put(words[i].charAt(j),pattern.charAt(j));

}

}

if(match)
{
result.add(words[i]);
}

}

return result;
}

On Sat, Jun 27, 2020 at 9:12 AM Daryl Wang <daryl...@gmail.com> wrote:

--

Priyank Gupta

unread,

Jun 27, 2020, 9:32:55 PM6/27/20

to leetcode-meetup

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

Please work on the problems at home and post your solutions to the thread. I will be discussing the answers on July 4th morning.
824
Goat Latin
63.0% Easy

Runtime: 32 ms, faster than 43.60% of Python3 online submissions for Goat Latin.
Memory Usage: 13.7 MB, less than 90.84% of Python3 online submissions for Goat Latin.
# Time : O(K*N) K -> length of each word N -> length of String
# Space : O(N)
class Solution:
def toGoatLatin(self, S: str) -> str:
vowel = {'a','e','i','o','u'}
words = S.split(' ')
for i in range(len(words)):
word = list(words[i])
if word[0].lower() not in vowel:
word.append(word.pop(0))
word.append('m')
word.append('a')
word += ['a']*(i+1)
words[i] = ''.join(word)
return ' '.join(words)

Priyank Gupta

unread,

Jun 27, 2020, 9:34:08 PM6/27/20

to leetcode-meetup

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

Please work on the problems at home and post your solutions to the thread. I will be discussing the answers on July 4th morning.

890
Find and Replace Pattern
73.2% Medium

Runtime: 24 ms, faster than 99.26% of Python3 online submissions for Find and Replace Pattern.

Memory Usage: 13.8 MB, less than 69.70% of Python3 online submissions for Find and Replace Pattern.

# Time : O(K*N) K-> no of words, N-> len of each word

# Space :O(N)

class Solution:

def isMatch(self, word, pattern):

if len(word) != len(pattern):

return 0

d1,d2 = {},{}

for i in range(len(word)):

if word[i] not in d1 and pattern[i] not in d2:

d1[word[i]] = pattern[i]

d2[pattern[i]] = word[i]

else:

if word[i] in d1:

if d1[word[i]] != pattern[i]:

return 0

else:

if d2[pattern[i]] != word[i]:

return 0

return 1

def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:

res = []

for word in words:

if self.isMatch(word,pattern):

res.append(word)

return res

Abhishek Kaukuntla

unread,

Jun 29, 2020, 12:15:28 AM6/29/20

to leetcode-meetup

824

Goat Latin

63.0%

Easy

/*

Date: 06/28/2020

Runtime: 7 ms, faster than 35.27% of Java online submissions for Goat Latin.

Memory Usage: 39.6 MB, less than 30.34% of Java online submissions for Goat Latin.

*/

class Solution {

private Set<Character> vowels;

public String toGoatLatin(String S) {

if (S == null) {

return S;

}

String[] words = S.split(" ");

int len = words.length;

StringBuilder ans = new StringBuilder();

for (int i=0; i<len; i++) {

String word = words[i];

if (!startingWithVowel(word)) {

word = word.substring(1) + word.charAt(0);

}

ans.append(word).append(appendGoatLatin(i)).append(i == len-1 ? "" : " ");

}

return ans.toString();

}

private String appendGoatLatin(int index) {

String gLatin = "ma";

for (int i=0; i<=index; i++) {

gLatin += 'a';

}

return gLatin;

}

private boolean startingWithVowel(String word) {

return vowels().contains(word.charAt(0));

}

private Set<Character> vowels() {

if (vowels == null) {

vowels = new HashSet<Character>();

vowels.add('a');

vowels.add('e');

vowels.add('i');

vowels.add('o');

vowels.add('u');

vowels.add('A');

vowels.add('E');

vowels.add('I');

vowels.add('O');

vowels.add('U');

}

return vowels;

}

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

karan alang

unread,

Jun 30, 2020, 2:42:00 AM6/30/20

to leetcode-meetup

lc824:

def toGoatLatin(self, S: str) -> str:

sList = S.split(' ')

res = ''

for idx, word in enumerate(sList):

# res += ' '

if word[0].lower() in {'a','e','i','o','u'}:

res += word+'ma'+'a'*(idx+1)+' '

else:

res += word[1:]+word[0]+'ma'+'a'*(idx+1)+' '

return res.rstrip()

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,

Jul 3, 2020, 7:12:16 PM7/3/20

to leetcode-meetup

824

Goat Latin

63.0%

Easy

Pretty straightforward problem. Main task is to break the string into words and transform each word according to the goat latin rules. The only particular note is we will always add 'ma' and 'a' to the end of the string. The only difference is whether the first letter is rotated back.

O(n) space

O(n) time

class Solution:

def toGoatLatin(self, S: str) -> str:

def goat_latin(word, index):

ans = word

if word[0] not in 'aeiouAEIOU':

ans = word[1:] + word[0]

ans += 'ma' + 'a' * index

return ans

words = S.split()

return ' '.join(goat_latin(word, i + 1) for i, word in enumerate(words))

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,

Jul 3, 2020, 7:22:17 PM7/3/20

to leetcode-meetup

890

Find and Replace Pattern

73.2%

Medium

We will check each word to see if it matches the pattern and will do this by actually building the mapping of letters between the pattern and a word. We keep a mapping of letters going from the word to the pattern, and a mapping from pattern to word. We iterate across letters in the word and pattern, and check that the mapping remains consistent for each pair of letters.

If the word letter is in the mapping from word to pattern, we checked that the mapped value is the same as the pattern letter we have. If not, then the word does not fit the pattern. We do the same check for the pattern letter going to word letter.

If both the word letter and pattern letter aren't in their respective mappings, then we set the mappings to point from one letter to the other.

If all letters pass the check, then the word matches the pattern and we can add it to the results.

O(total sum of all words) time
O(largest word) space

class Solution:

def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:

def pattern_p(word):

word_mapping = {}

pattern_mapping = {}

for word_letter, pattern_letter in zip(word, pattern):

if word_letter not in word_mapping and pattern_letter not in pattern_mapping:

word_mapping[word_letter] = pattern_letter

pattern_mapping[pattern_letter] = word_letter

elif word_mapping.get(word_letter, '') != pattern_letter or pattern_mapping.get(pattern_letter, '') != word_letter:

return False

return True

return filter(pattern_p, words)

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,

Jul 3, 2020, 7:47:06 PM7/3/20

to leetcode-meetup

899

Orderly Queue

51.5%

Hard

The actually coding of this problem is simple: for the K=1 case, keep rotating the first letter of the string to the back, and return the lowest rotation. For K>=2, then the result is just the sorted string. This is easy to implement, but recognizing this is the difficult part of the problem.

The key insight is that it is possible to swap any two letters in the string when K>=2. Assume that we have the string ***AB****, where * are arbitrary letters that we don't care about for this example. It is possible to get ***BA****, where A and B have swapped places.

We start by constantly moving the first of the letter of the string back, until we get:

**AB*****

*AB******

AB*******

At this point, we can move B, the second letter in the string, to the back of the string.

A*******B

We can then move A to the back of the string:

*******BA.

We can then keep moving the first letter of the string back until the BA pair is in the proper position:

******BA*

*****BA**

****BA***

***BA****

After n swaps, we have now successfully swapped two adjacent letters. Now that we have the ability to swap any two adjacent letters, we can just run bubble sort to get a sorted list. Any case of K > 2 just boils down to the K=2 case, just with the potential to use less moves. This is a very slow way to get to the sorted result, but it is a simple proof that the sorted result is possible. We can then use a much more efficient sorting algorithm in the actual code.

O(n) space

O(nlog(n)) time

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

karan alang

unread,

Jul 13, 2020, 2:36:31 AM7/13/20

to leetcode-meetup

lc890:

def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:

def checkPattern(word):

if len(set(word)) != len(set(pattern)):

return False

d = {}

for i in range(len(word)):

if d.get(word[i]) == None:

d[word[i]] = pattern[i]

elif d.get(word[i]) != None and d[word[i]] != pattern[i]:

return False

return True

res = []

for word in words:

if checkPattern(word):

res.append(word)

return res

On Saturday, June 27, 2020 at 9:12:39 AM UTC-7, Daryl Wang wrote:

Reply all

Reply to author

Forward