273. Integer to English Words

Difficulty: Medium

Frequency: 

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

  1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
  2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
  3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

My solution:
Data structure:
string, unordered_map
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
1. 0
2. 1000010
3. 10
4. 30
5. 100
6. 1000
Code:
class Solution {
public:
    string digits[20] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    string tens[10] = {"Zero", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

    string int2string(int n) {
        if (n >= 1000000000) {
            return int2string(n / 1000000000) + " Billion" + int2string(n % 1000000000);
        } else if (n >= 1000000) {
            return int2string(n / 1000000) + " Million" + int2string(n % 1000000);
        } else if (n >= 1000) {
            return int2string(n / 1000) + " Thousand" + int2string(n % 1000);
        } else if (n >= 100) {
            return int2string(n / 100) + " Hundred" + int2string(n % 100);
        } else if (n >= 20) {
            return  " " + tens[n / 10] + int2string(n % 10);
        } else if (n >= 1) {
            return " " + digits[n];
        } else {
            return "";
        }
    }

    string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        } else {
            string ret = int2string(num);
            return ret.substr(1, ret.length() - 1);
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

049. 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.


Questions:

1. results need to be sorted or not.
2. upper case and lower case consideration.

Test cases:

1. empty input

2. single input

3. all different anagrams

4. all same anagram

5. normal case


 Solution 1:

Data structure:
string, vector, unordered_map
Method:
hash table
Steps:
1. for each string, sort it.
2. add the original string to the hash table with sorted string as key.
Complexity:
runtime: O(NlogN)
space:O(N)
Code:
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> myMap;
        //loop through the input
        for (auto str : strs) {
            string s = str;
            sort(s.begin(), s.end());
            myMap[s].push_back(str);
        }

        //construct the results
        vector<vector<string>> results;
        for (auto iter : myMap) {
            results.push_back(iter.second);
        }
        return results;
    }
};

Solution 2:
Data structure:
array, string, unordered_map
Method:
hash table
steps:
1. generate a unique string from the input string as a key
2. insert into the hash table
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> myMap;
        //loop through the input strings
        for (string str : strs) {
            //construct the key based on the number of characters in the string
            vector<int> cnt(26, 0);
            string key = "";
            for (char c : str) {
                ++cnt[c - 'a'];
            }
            for (int i : cnt) {
                key += to_string(i) + "#";
            }
            myMap[key].push_back(str);
        }

        //construct the results
        vector<vector<string>> results;
        for (auto iter : myMap) {
            results.push_back(iter.second);
        }

        return results;
    }
};

Things to learn:
1. the way to generate the key in solution 2 is interesting. For infinite input, there may be an easier solution.

249. (Locked)Group Shifted Strings

Difficulty:  Easy

Frequency: N/A

Given a string, we can “shift” each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep “shifting” which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Note: For the return value, each inner list’s elements must follow the lexicographic order.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {  
public:  
    vector<vector<string>> groupStrings(vector<string>& strings) {  
        unordered_map<string, vector<string>> d;  
        for(int i = 0; i < strings.size(); i++) {  
            string s = "";  
            for(int j = 0; j < strings[i].size(); j++) {  
                s += to_string(((strings[i][j] - strings[i][0]) + 26) % 26) + " ";  
            }  
            if(d.find(s) != d.end()) {  
                d[s].push_back(strings[i]);  
            } else {  
                vector<string> v;  
                v.push_back(strings[i]);  
                d.insert(pair<string, vector<string>>(s, v));  
            }  
        }  
          
        vector<vector<string>> results;
        for(vector<vector<string>>::iterator i = d.begin(); i != d.end(); i++) {  
            sort(i->second.begin(), i->second.end());  
            results.push_back(i->second);  
        }  
        return results;  
    }  
};  

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

170. (Locked)Two Sum III – Data structure design

Difficulty: Easy

Frequency: N/A 

Design and implement a TwoSum class. It should support the following operations: add and find.

add(input) – Add the number input to an internal data structure.
find(value) – Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5); find(4)true; find(7)false


Solution 1:
Data structure:
unordered_map
Complexity:
Time:
add: O(1)
find: O(n) worst case  —->not O(1) ? average
Space: O(n)
Code:

class two_sum {
         unordered_map&lt;int, int&gt; num_count_map;

          void add(int new_num) {
                   if (num_count_map[new_num]) {
                             num_count_map[new_num] = num_count_map[new_num] + 1;
                   } else {
                             num_count_map[new_num] = 1;
                   }
          }

          bool find(int target) {
                   unordered_map&lt;int, int&gt;::iterator map_iter;
                   for (map_iter = num_count_map.begin(); map_iter != num_count_map.end(); map_iter++) {
                             int num_to_find = target - map_iter-&gt;first;
                             if (num_count_map.find(num_to_find)) {
                                       if (num_to_find != map_iter-&gt;first) {
                                                 return true;
                                       } else {
                                                 if (map_iter-&gt;second &gt; 1) {
                                                          return true;
                                                 }
                                       }
                             } else {
                                       return false;
                             }
                    }
          }
}

Things to learn:

159. (Locked)Longest Substring with At Most Two Distinct Characters

Difficulty: Hard

Frequency: N/A

Given a string S, find the length of the longest substring T that contains at most two distinct characters.

For example,
Given S = “eceba”,
T is “ece” which its length is 3.


Solution 1:
Data structure:
string, unordered_map
Steps:
1. Loop through the string using head and tail index to keep a sliding window.
2. For each char in the string
  2.1 If it is not in the map, insert it, num_distinct++
  2.2 map[s[tail]]++
  2.3 while (num_distinct > 2) map[s[head]]–
    2.3.1 If map[s[head]] == 0, num_distince–
    2.3.2 head++
  2.4 max_length = max(tail – head + 1, max_length)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
Corner cases:
Code:
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int max_length = 0, head = 0, num_distinct = 0;
        unordered_map&lt;char, int&gt; count_map;
        for (int tail = 0; tail &lt; s.size(); tail++) {
            if (!count_map.count(s[tail])) {
                num_distinct++;
            }
            count_map[s[tail]]++;
            while (distinct &gt; 2) {
                count_map[s[head]]--;
                if (!count_map.count([s[head]]))
                    num_distinct--;
                i++;
            }
            max_length = max(max_length, tail - head + 1);
        }
        return max_length;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

013. Roman to Integer

Difficulty: Easy

Frequency: N/A

My solution:
Data structure:
unordered_map,string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
class Solution {
public:
    int romanToInt(string s) {
        unordered_map&lt;char, int&gt; roman_map = {{'I', 1},
                                              {'V', 5},
                                              {'X', 10},
                                              {'L', 50},
                                              {'C', 100},
                                              {'D', 500},
                                              {'M', 1000}};
        int result = 0;
        for (int i = 0; i &lt; s.size(); i++) {
            if (i != s.size() &amp;&amp; roman_map[s[i]] &lt; roman_map[s[i + 1]]) {
                result -= roman_map[s[i]];
            } else {
                result += roman_map[s[i]];
            }
        }
        return result;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

003. Longest Substring Without Repeating Characters

 Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Questions:

1. upper case and lower case characters are same or not?

2. whether there is only 1 solution.


Test cases:

1. empty string
2. a
3. bbbbbb
4. abcabcbcbb: dup is in the window
5. tmmzuxt: dup is not in the window

Solution 1:

Data structure:
string, unordered_map
Method:
two pointers, hash table
Steps:
1. loop through the string using head and tail, for each char
  2.1 fix head, move tail
  2.1 if it is not in the hash map, insert(char, index)
  2.2 if it is in the hash map, and index >= head, move head to old_index + 1, and replace with new index,
  2.2 max_length = max(max_length, tail – head + 1)
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (!n) return 0;
        unordered_map<char, int> m;
        int head = 0, tail = 0, result = 0;
        while (tail < n) {
            if (m.find(s[tail]) != m.end() && m[s[tail]] >= head) {
                    head = m[s[tail]] + 1;
            }
            m[s[tail]] = tail;
            result = max(result, tail - head + 1);
            tail++;
        }
        return result;
    }
};

Solution 2:
Data structure:
string, array
Method:
two pointers
Steps:
same with Method 1, but using array instead of unordered_map.
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (!n) return 0;
        vector<int> m(256, -1);
        int head = 0, tail = 0, result = 0;
        while (tail < n) {
            head = max(head, m[s[tail]] + 1);
            m[s[tail]] = tail;
            result = max(result, tail - head + 1);
            tail++;
        }
        return result;
    }
};

Submission errors:

1. wrong answer. Did not consider the case that dup is not in the window.

Things to learn:
1. good test case can help find bug.
2. when input range is known, we can use array instead of hash map to improve the performance.
3. the ASCII table has 128 characters, with values from 0 through 127. Thus, 7 bits are sufficient to represent a character in ASCII; however, most computers typically reserve 1 byte, (8 bits), for an ASCII character.