leetCode Question: Bulls and Cows

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number: "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:

Secret number: "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Analysis:

It is not hard to discover that if we search the number and guess pair, a "bull" is straightforward to check and count, and also once we have a "bull", it can be viewed as "consumed". We don't have to store it anymore and it will not effect the counting for "cows".

Now the only problem is to handle the "cows". We could use hash map (hash table) to store the count numbers in secret and guess, respectively. It is OK to keep one hash table and search the sequence multiple times. Here, we want to search the whole sequence just once for better efficiency, two hash table are kept.

There are several cases when we go through the sequence and compare the number in secret (denoted as s[ ] ) and guess (denoted as g[ ] ), we also denote mp_s as the hash map for s[ ] and mp_g as the hash map for g[ ]:

• s [ i ] == g [ i ], then it is a "cow", just add the cow count.

• s [ i ] != g [ i ], the below 4 sub cases indicated that: We have the number g[ i ] at hand, check if it has occurred in secret. And then we have the number s[ i ] at hand, check if it has occurred in guess.

  • mp_s[ g[i] ] doesn't exist. It means currently g[i] is not a bull, but we are not sure if it is a bull in the future. E.g.,
    s = [1 2 0 3]
    g = [3 2 0 0]
    when i = 0, 1 != 3, 3 is not a bull for now, but 3 is a bull if we search until the end of sequence.
    Thus, we have to save the g[ i ] in mp_g for later.
  • mp_s[ g[i] ] exists and > 0. It means there is a char g[ i ] in the secret sequence, that is a "bull". So we subtract the value stored in mp_s[ g[i] ] and add the bull count. The reason of >0 condition is for the case of duplicates, if we have already consumed a "bull", the key is still there but value might be <= 0.
  • mp_g[ s[ i ] ] doesn't exist. Similarly, we also store the s[ i ] for later. E.g,
    s = [1 8 0 7]
    g = [5 8 1 6]
    when i = 0, s[i] = 1, which has no match, but later when i = 2, g[ 2 ]=1. g[ 2 ] and s[ 0 ] is a "bull".
  • mp_g[ s[i] ] exists and >0.

Code(C++):

class Solution {

public:

string getHint(string secret, string guess) {

int b = 0;

int c = 0;

int mp1[10] = {0,0,0,0,0,0,0,0,0,0};

int mp2[10] = {0,0,0,0,0,0,0,0,0,0};

for (int i=0;i<secret.size();i++){

if (secret[i] == guess[i]) {

b += 1;

}else{

if (mp1[guess[i]-'0']==0){

mp2[guess[i]-'0'] +=1;

}else{

mp1[guess[i]-'0'] -=1;

c += (mp1[guess[i]-'0']>=0);

}

if (mp2[secret[i]-'0']==0){

mp1[secret[i]-'0'] +=1;

}else{

mp2[secret[i]-'0'] -=1;

c += (mp2[secret[i]-'0']>=0);

}

}

}

return to_string(b) + "A" + to_string(c) + "B";

}

};

Code(Python):

class Solution(object):

def getHint(self, secret, guess):

"""

:type secret: str

:type guess: str

:rtype: str

"""

b = 0

c = 0

mp1 = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

mp2 = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

for i in range(len(secret)):

s = secret[i]

g = guess[i]

if s == g:

b += 1

else:

if mp1[g] == 0:

mp2[g] += 1

else:

mp1[g] -= 1

c += mp1[g]>=0

if mp2[s]==0:

mp1[s] += 1

else:

mp2[s] -= 1

c += (mp2[s]>=0)

return str(b) + "A" + str(c) + "B"

leetCode Question: Word Pattern

Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Analysis:

This problem is not hard but needs you be more careful with all the conditions:

• The length of the words in str and chars in pattern may be different
• The char to word is a bijection, which means it is a one-to-one mapping.
• Don't forget to handle the last word when you split the str.

Here for the bijection mapping, I just used two maps, one save (word, char), and the other to save (char, word).

Code (C++):

class Solution {

public:

bool wordPattern(string pattern, string str) {

map<char, string> mp1;

map<string, char> mp2;

string tmp = "";

int j = 0;

for (int i=0;i<=str.size();i++){

if (j == pattern.size()){ return false; }

if (str[i]==' ' || i == str.size()){

if (mp1.find(pattern[j]) == mp1.end() && mp2.find(tmp) == mp2.end()){

mp1[pattern[j]] = tmp;

mp2[tmp] = pattern[j++];

}else{

if (mp1[pattern[j]] == tmp && mp2[tmp] == pattern[j]){ j++; }

else{ return false; }

}

tmp = "";

}else{

tmp += str[i];

}

}

if (j != pattern.size()){return false;}

return true;

}

};

Code (Python):

class Solution(object):

def wordPattern(self, pattern, str):

"""

:type pattern: str

:type str: str

:rtype: bool

"""

mp1 = {}

mp2 = {}

words = str.split(' ')

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

return False

for word, ch in zip(words, pattern):

if word not in mp1 and ch not in mp2:

mp1[word] = ch

mp2[ch] = word

elif mp1.get(word) == ch and mp2.get(ch) == word:

pass

else:

return False

return True

leetCode Question: H-Index

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Analysis:

This problem is pretty straightforward.The easist way which requires more time is sorting the array, the time complexity will be O(n log n) (we ignore this method in this post).

Another way is to use more space, but we can get O(n) time, which is faster than the sorting approach. Thinking about the definition of H-index, the max number of h is the number of paper we have. So we could use a map (or vector in my case), to store: if current paper has i citations, we add map[i] by 1. Note that if citation is more than the number of papers, we added 1 to the last index of the map.

In this way, for each key i in our map, we only need to add the sum of all values afer i to the end, we will know how many papers are there have more then i citations. The maximum i is what we want.

Code (C++):

class Solution {

public:

int hIndex(vector<int>& citations) {

int ssum = 0;

int sz = citations.size();

vector<int>mp(sz+1,0);

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

mp[min(sz,citations[i])] +=1;

}

for (int i=sz;i>=0;--i){

ssum += mp[i];

if (ssum >= i){return i;}

}

return 0;

}

};

Code (Python):

class Solution(object):

def hIndex(self, citations):

"""

:type citations: List[int]

:rtype: int

"""

ssum = 0

sz = len(citations)

mp = [0]*(sz+1)

for ci in citations:

mp[min(sz,ci)] +=1

for i in range(sz,-1,-1):

ssum += mp[i]

if ssum>=i:

return i

return 0

leetcode Question: Group Anagrams

Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

Analysis:

In the problem of anagram, hash map is quite often used to efficiently get us to the correct answer.

For this specific quesion, the key is how we set the key to the map so that for each str in the array, the key can be efficiently computed.

One slower version is to use the sorted string as the key, and for each string  a sort operation is required to compute the key. The complexity is O(n * m log m) where n is the number of strings, and m is the length of each string. 

However, another way of compute the key is more efficient, we could speed up the complexity to O(n * m).

Thinking about the prime numbers, for each char in the string, we can compute the multiplication for one prime number corresponding to the char. In such way, only anagram strings become the same number.  For the prime numbers, we can just precompute since there are only 26 prime numbers we need.

Slow Code (C++):

class Solution {

public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {

vector<vector<string>> res;

map<string, vector<string> > mp;

for (int i=0;i<strs.size();++i){

string key = strs[i];

sort(key.begin(), key.end());

if (mp.find(key) == mp.end()){

mp[key] = vector<string>(1,strs[i]);

}else{

mp[key].push_back(strs[i]);

}

}

for (auto it = mp.begin(); it !=mp.end(); it++){

res.push_back(it->second);

}

return res;

}

};

Code (C++):

class Solution {

public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {

vector<vector<string>> res;

int primes[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

map<int, int> mp;

int key;

int count = 0;

for (int i=0; i<strs.size();++i){

key = 1;

for (int j=0; j < strs[i].size();++j){

key *= primes[strs[i][j]-'a'];

}

if (mp.find(key) == mp.end()){

mp[key] = count++;

res.push_back(vector<string>(1, strs[i]));

}else{

res[mp[key]].push_back(strs[i]);

}

}

return res;

}

};

Code(Python):

class Solution(object):

def groupAnagrams(self, strs):

"""

:type strs: List[str]

:rtype: List[List[str]]

"""

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

mp = {}

res = []

count = 0

for str in strs:

key = 1

for ch in str:

key *= primes[ord(ch) - ord('a')]

if mp.get(key) is None:

mp[key] = count

res.append([str])

count += 1

else:

res[mp[key]].append(str)

return res