(Multiply Strings)

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

Thoughts:
This is not a hard question in the sense that there’s no “clever” algorithm to apply. We just do the intuitive way. Think about how we human being multiply two integers. We take each digit and multiply it with another digit, then the addition, taking care of the carry. So we just “mimic” that method in our code. The only catch is that we have to be busy travelling between integer and char. Another catch is how much space we should initialize our result string. Well, in my solution, I try to be conservative to find the upper bound – the number of digits of the products can be no more than the sum of the digits of the two multipliers. In the end, we might find we allocated more space than we need to, resulting some leading zeros. We can just clean it up.

Code (Java):

public class Solution {
    public String multiply(String num1, String num2) {
        char[] result = new char[num1.length() + num2.length()];
        for(int i = 0; i < result.length; ++i)
            result[i] = '0';
        for(int i = num1.length() - 1; i >= 0; --i) {
            int index = num1.length() + num2.length() - 1 - (num1.length() - 1 - i);
            int digit1 = Character.getNumericValue(num1.charAt(i));
            for(int j = num2.length() - 1; j >= 0; --j) {
                int digit2 = Character.getNumericValue(num2.charAt(j));
                int temp = digit1 * digit2;
                int previous = Character.getNumericValue(result[index]);
                result[index] = (char) ((previous + temp) % 10 + '0');
                int carry = (previous + temp) / 10;
                int m = index - 1;                
                while(carry != 0 && m >= 0) {
                    int rm = Character.getNumericValue(result[m]);
                    result[m] = (char)((rm + carry) % 10 + '0');
                    carry = (rm + carry) / 10;
                    m--;
                }
                
                index--;
            }
        }
        return new String(result).replaceFirst("^0+(?!$)", "");
    }
}

Code (C++):

class Solution {
public:
    string multiply(string num1, string num2) {
        char result[num1.size() + num2.size()];
        for(int i = 0; i < num1.size() + num2.size(); ++i)
            result[i] = '0';
        for(int i = num1.size() - 1; i >= 0; --i) {
            int index = num1.size() + num2.size() - 1 - (num1.size() - 1 - i);
            int digit1 = num1[i] - '0';
            for(int j = num2.size() - 1; j >= 0; --j) {
                int digit2 = num2[j] - '0';
                int temp = digit1 * digit2;
                int previous = result[index] - '0';
                result[index] = (char) ((previous + temp) % 10 + '0');
                int carry = (previous + temp) / 10;
                int m = index - 1;                
                while(carry != 0 && m >= 0) {
                    int rm = result[m] - '0';
                    result[m] = (char)((rm + carry) % 10 + '0');
                    carry = (rm + carry) / 10;
                    m--;
                }
                
                index--;
            }
        }
        string candidate = string(result, num1.size() + num2.size());
        size_t i = candidate.find_first_not_of('0');
        return i ==  string::npos ? "0" : candidate.substr(i);
    }
};
Advertisements

(Minimum Window Substring)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Thoughts:
The idea is from here. I try to rephrase it a little bit here. The general idea is that we find a window first, not necessarily the minimum, but it’s the first one we could find, traveling from the beginning of S. We could easily do this by keeping a count of the target characters we have found. After finding an candidate solution, we try to optimize it. We do this by going forward in S and trying to see if we could replace the first character of our candidate. If we find one, we then find a new candidate and we update our knowledge about the minimum. We keep doing this until we reach the end of S. For the giving example:

  1. We start with our very first window: “ADOBEC”, windowSize = 6. We now have “A”:1, “B”:1, “C”:1
  2. We skip the following character “ODE” since none of them is in our target T. We then see another “B” so we update “B”:2. Our candidate solution starts with an “A” so getting another “B” cannot make us a “trade”.
  3. We then see another “A” so we update “A”:2. Now we have two “A”s and we know we only need 1. If we keep the new position of this “A” and disregard the old one, we could move forward of our starting position of window. We move from A->D->O->B. Can we keep moving? Yes, since we know we have 2 “B”s so we can also disregard this one. So keep moving until we hit “C”: we only have 1 “C” so we have to stop. Therefore, we have a new candidate solution, “CODEBA”. Our new map is updated to “A”:1, “B”:1, “C”:1.
  4. We skip the next “N” and we arrive at “C”. Now we have two “C”s so we can move forward the starting position of last candidate: we move along this path C->O->D->E until we hit “B”. We only have one “B” so we have to stop. We have yet another new candidate, “BANC”.
  5. We have hit the end of S so we just output our best candidate, which is “BANC”.

Code (Java):

public class Solution {
    public String minWindow(String S, String T) {
        int[] needToFind = new int[256];
        int[] hasFound = new int[256];
        
        for(int i = 0; i < T.length(); ++i) {
            needToFind[T.charAt(i)]++;
        }
        
        int count = 0;
        int minWindowSize = Integer.MAX_VALUE;
        int start = 0, end = 0;
        String window = "";
        
        for(; end < S.length(); end++) {
            if(needToFind[S.charAt(end)] == 0) continue;
            char c = S.charAt(end);
            hasFound[c]++;
            
            if(hasFound[c] <= needToFind[c]) {
                count++;
            }
            
            if(count == T.length()) {
                while(needToFind[S.charAt(start)] == 0 ||
                    hasFound[S.charAt(start)] > needToFind[S.charAt(start)]) {
                    if(hasFound[S.charAt(start)] > needToFind[S.charAt(start)])
                        hasFound[S.charAt(start)]--;
                    start++;
                }
                
                if(end - start + 1 < minWindowSize) {
                    minWindowSize = end - start + 1;
                    window = S.substring(start, end + 1);
                }
            }
        }
        
        return window;
    }
}

Code (C++):

class Solution {
public:
    string minWindow(string S, string T) {
        int needToFind[256] = {0};
        int hasFound[256] = {0};
        
        for(int i = 0; i < T.size(); ++i) {
            needToFind[T[i]]++;
        }
        
        int count = 0;
        int minWindowSize = INT_MAX;
        int start = 0, end = 0;
        string window;
        
        for(; end < S.size(); end++) {
            if(needToFind[S[end]] == 0) continue;
            hasFound[S[end]]++;
            
            if(hasFound[S[end]] <= needToFind[S[end]]) {
                count++;
            }
            
            if(count == T.size()) {
                while(needToFind[S[start]] == 0 ||
                    hasFound[S[start]] > needToFind[S[start]]) {
                    if(hasFound[S[start]] > needToFind[S[start]])
                        hasFound[S[start]]--;
                    start++;
                }
                
                if(end - start + 1 < minWindowSize) {
                    minWindowSize = end - start + 1;
                    window = S.substr(start, minWindowSize);
                }
            }
        }
        
        return window;
    }
};

(String to Integer (atoi))

Implement atoi to convert a string to an integer.

Thoughts:
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Code (Java):

	public int atoi(String number) {
		if (number == null || number.trim().length() == 0) {
			return 0;
		}

		int result = 0;
		number = number.trim();

		boolean negate = false;
		char sign = number.charAt(0);

		if (sign == '+' || sign == '-') {
			if (sign == '-') {
				negate = true;
			}
			number = number.substring(1);
		}

		int length = number.length();
		int start = -1;
		int index = 0;
		for (; index < length; index++) {
			char a = number.charAt(index);
			if (a >= '0' && a <= '9') {
				if (start == -1)
					start = index;
			} else {
				break;
			}
		}
		int end = index - 1;

		if (start == -1)
			return 0;

		for (int i = start; i <= end; ++i) {
			char a = number.charAt(i);
			int digit = a - '0';
			if (!negate) {
				if (result + digit * (int) Math.pow(10, end - i) >= result)
					result += digit * (int) Math.pow(10, end - i);
				else
					result = Integer.MAX_VALUE;
			} else {
				if (result - digit * (int) Math.pow(10, end - i) <= result)
					result -= digit * (int) Math.pow(10, end - i);
				else
					result = Integer.MIN_VALUE;
			}
		}

		return result;
	}

Code (C++):

class Solution {
public:
    int atoi(const char *str) {
        if (str == NULL) {
            return 0;
        }
        string number(str);
        if(number.size() == 0)
            return 0;
        
        int i = 0;
        for(; i < number.size(); ++i) {
            if(!isspace(number[i])) {
                break;
            }
        }
        number = number.substr(i);
        int result = 0;
        
        bool negate = false;
        char sign = number[0];

        if (sign == '+' || sign == '-') {
            if (sign == '-') {
                negate = true;
            }
            number = number.substr(1);
        }

        int length = number.size();
        int start = -1;
        int index = 0;
        for (; index < length; index++) {
            char a = number[index];
            if (a >= '0' && a <= '9') {
                if(start == -1)
                    start = index;
            } else {
                break;
            }
        }
        int end = index - 1;

        if (start == -1)
            return 0;

        for (int i = start; i <= end; ++i) {
            char a = number[i];
            int digit = a - '0';
            if (!negate) {
                if (result + digit * (int) pow(10, end - i) >= result)
                    result += digit * (int) pow(10, end - i);
                else
                    result = INT_MAX;
            } else {
                if (result - digit * (int) pow(10, end - i) <= result)
                    result -= digit * (int) pow(10, end - i);
                else
                    result = INT_MIN;
            }
        }

        return result;
    }
};

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

Thoughts:
We want to finish this task in one scan. We can maintain a hashtable to detect if we have seen any character. We start from the beginning and walk through the array until we hit a repetition, let’s say, at position i. We then have two piece of valuable information right now:

  1. s[0..i-1] is a candidate of the longest substring without repetition. Therefore we can update the max length.
  2. There exists a position 0 \leq j \leq i-1, such that s[j] == s[i]. Substring starting from j is not a candidate because it has at least one repetition: s[j] and s[i]. Any substring ended at j will be shorter than the substring s[0..i-1] so we don’t need to look at them.

Then we can remove every elements in the hashtable from 0 to j, and make the start position of next candidate to j + 1. We keep walking and repeating this process until we hit the last element.

Code (Java):

import java.util.HashSet;
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        int candidateStartIndex = 0;
        for(int iter = 0; iter < s.length(); ++iter) {
            char c = s.charAt(iter);
            if(set.contains(c)) {
                max = Math.max(max, iter - candidateStartIndex);
                while(s.charAt(candidateStartIndex) 
                        != s.charAt(iter)) {
                    set.remove(s.charAt(candidateStartIndex));
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                set.add(c);
            }
        }
        max = Math.max(max, s.length() - candidateStartIndex);
        return max;
    }
}

Code (C++):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unsigned int maxLen = 0;
        set<char> hashtable;
        int candidateStartIndex = 0;
        for(unsigned int iter = 0; iter < s.size(); ++iter) {
            char c = s[iter];
            if(hashtable.find(c) != hashtable.end()) {
                maxLen = max(maxLen, iter - candidateStartIndex);
                while(s[candidateStartIndex] != s[iter]) {
                    hashtable.erase(s[candidateStartIndex]);
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                hashtable.insert(c);
            }
        }
        maxLen = max(maxLen, s.size() - candidateStartIndex);
        return maxLen;
    }
};

(Longest Palindromic Substring)

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Thoughts:
Two parts of this question: determine if a string is palindrome and find out the longest palindrome. First part can be done in recursive or iterative way. We just need to check if the 1st letter == last letter, 2nd letter == 2nd last letter, so on and so forth. Second part we can do it using a sliding window approach. We examine if the entire string is palindrome or not, then the substrings of length n – 1 (there are two of them), then the substrings of length n – 2 (3 of them), etc.

Code (Java):

public class Solution {
    public String longestPalindrome(String s) {
        for(int len = s.length(); len > 0; --len) {
            for(int j = 0; j <= s.length() - len; ++j) {
                String sub = s.substring(j, j + len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return new String();
    }
    
    private boolean isPalindrome(String s) {
        if(s.length() <= 1)
            return true;
        else
            return s.charAt(0) == s.charAt(s.length()-1) && 
                isPalindrome(s.substring(1,s.length()-1));
    }
}

Code (C++):

class Solution {
public:
    string longestPalindrome(string s) {
        for(int len = s.size(); len > 0; --len) {
            for(int i = 0; i <= s.size() - len; ++i) {
                string sub = s.substr(i, len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return "";
    }
    
private:
    bool isPalindrome(string s) {
        if(s.size() <= 1)
            return true;
        else
            return s[0] == s[s.size() - 1] && 
            isPalindrome(s.substr(1,s.size()-2));
    }
};

Find the longest common prefix in an array of strings (Longest Common Prefix)

Write a function to find the longest common prefix string amongst an array of strings.

Thoughts:
Apparently this can be done in O(n). We start with the first string as the longest common prefix. We then go through every string in the array and compare the prefix with them. Update (shorten) the prefix if needed.

Code (Java):

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix = new String();
        if(strs.length > 0)
            prefix = strs[0];
        for(int i = 1; i < strs.length; ++i) {
            String s = strs[i];
            int j = 0;
            for(; j < Math.min(prefix.length(), s.length()); ++j) {
                if(prefix.charAt(j) != s.charAt(j)) {
                    break;
                }
            }
            prefix = prefix.substring(0, j);
        }
        return prefix;
    }
}

Code (C++):

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        string prefix;
        if(strs.size() > 0)
            prefix = strs[0];
        for(int i = 1; i < strs.size(); ++i) {
            string s = strs[i];
            int j = 0;
            for(; j < min(prefix.size(), s.size()); ++j) {
                if(prefix[j] != s[j])
                    break;
            }
            prefix = prefix.substr(0, j);
        }
        return prefix;
    }
};

(Letter Combinations of a Phone Number)

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Thoughts:
Another classic recursion problem. We try to generate solution each time by iterating through every digit and every character that digit maps to. If we overflow, we cut that solution and stop. If we get the correct solution (where solution.length() == digits.length()), we add to the solution set.

Code (Java):

public class Solution {
    private HashMap<Character, String> map;
    
    public ArrayList<String> letterCombinations(String digits) {
        setup();
        ArrayList<String> solutions
            = new ArrayList<String>();
        recursion(digits, 0, new String(), solutions);
        return solutions;
    }
    
    private void recursion(String digits, int start, 
        String sol, ArrayList<String> solutions) {
        if(sol.length() > digits.length()) {
            return;  
        } else if(sol.length() == digits.length()) {
            solutions.add(sol);
            return;
        } else {
            for(int i = start; i < digits.length(); ++i) {
                String letters = map.get(digits.charAt(i));
                for(int j = 0; j < letters.length(); ++j) {
                    recursion(digits, i + 1, sol + letters.charAt(j), solutions);
                }
            }
        }
    }
    
    private void setup() {
        map = new HashMap<Character, String>();
        map.put('1', "");
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        map.put('0', " ");
    }
}

Code (C++):

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        setup();
        vector<string> solutions;
        string s;
        recursion(digits, 0, s, solutions);
        return solutions;
    }
    
private:
    map<char, string> mapping;
    void recursion(string digits, int start, 
        string sol, vector<string>& solutions) {
        if(sol.size() > digits.size()) {
            return;  
        } else if(sol.size() == digits.size()) {
            solutions.push_back(sol);
            return;
        } else {
            for(int i = start; i < digits.size(); ++i) {
                string letters = mapping[digits[i]];
                for(int j = 0; j < letters.size(); ++j) {
                    recursion(digits, i + 1, sol + letters[j], solutions);
                }
            }
        }
    }
    
    void setup() {
        mapping.clear();
        mapping['1'] = "";
        mapping['2'] = "abc";
        mapping['3'] = "def";
        mapping['4'] = "ghi";
        mapping['5'] = "jkl";
        mapping['6'] = "mno";
        mapping['7'] = "pqrs";
        mapping['8'] = "tuv";
        mapping['9'] = "wxyz";
        mapping['0'] = " ";
    }
};

Previous Older Entries