[LeetCode] Different ways to add parentheses

Problem statement (link):

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Analysis:

This problem statement is a bit misleading (in a good way) so that my first attempt is to construct the different parenthesesed strings, and compute each string individually. This approach is exponential in both space and time complexity.

Now, the problems that ask for "all possible results" is usually solved using DFS approach. Don't get confused about the * operator as it would be treated equivalently as the + and - because of the parentheses. In the end, all the question asks is to find all possible combinations using parentheses.

With that, we could construct the solutions bottom-up. It's exactly the same as Unique Binary Tree II problem if we think each node as an arithmetic string. For instance,  in Example 2, we have the following ways of constructing the solutions:

Recursion Trees:
1)
                                        2 * 3 - 4 * 5
                                      /                     \
                                   2                   3 - 4 * 5
                                                       /             \
                                                     3             4 * 5
                                                                     /     \
                                                                    4      5
2)
                                        2 * 3 - 4 * 5
                                      /                     \
                                 2 * 3                  4 * 5
                                /       \                 /        \
                              2          3            4           5
3) ...
4) ...
5) ...

You get the idea.

Only extra work we need to do is instead of connecting the nodes, we compute each node (arithmetic string). The time complexity is still exponential but the code looks very clean.

Code:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i=0; i<input.length(); i++) {
            char c = input.charAt(i);
            if (c=='+' || c=='-' || c=='*') {
                for (Integer int1: diffWaysToCompute(input.substring(0, i))) {
                    for (Integer int2: diffWaysToCompute(input.substring(i+1))) { // i+1: to skip the operator char
                        res.add(c=='+' ? int1+int2 : c=='-' ? int1-int2 : int1*int2);
                    }
                }
            }
        }

        if (res.size()==0)
            res.add(Integer.parseInt(input));
        return res;
    }
}

[LeetCode] Generate Parentheses

Problem Statement (link):

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:
The problem asks for all combinations, this usually indicates it's a DFS problem.

In the recursion function, if we've used up all left and right parentheses, we push the formed string into result vector. Otherwise, we can add either left parentheses or right parentheses. The code for this problem is shown in Sol 1 below.

The extended version of this problem is that instead of only having parentheses, we are given n1 parentheses pairs, n2 bracket pairs, and n3 curly parentheses, and we are asked for the same thing - all combinations.

The idea is pretty similar to the simple version. The only difference is that we can do one of the following:
1) add left parentheses '(';
2) add left bracket '[';
3) add left curly parentheses '{';
4) add the right part, depending on the left situation, we choose either ')', ']', or '}'.

The code is shown in Sol 2 below.

Code:
Sol 1:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n<1) return res;
        dfs(res, "", "", n);
        return res;
    }
    void dfs(vector<string> &res, string left, string tmp, int n) {
        if (left.size()==0 && n==0) {
            res.push_back(tmp);
            return;
        }
        if (n>0) {
            dfs(res, "("+left, tmp+"(", n-1);
        }
        if (left.size()>0) {
            dfs(res, left.substr(1), tmp+")", n);
        }
    }
};

Sol 2:

string rightPart(string left) {
    if (left=="(") return ")";
    else if (left=="[") return "]";
    else return "}";
}

void dfsParen(vector<string> &res, string leftStack, string str, int n1, int n2, int n3) {
    if (leftStack.empty() && n1==0 && n2==0 && n3==0) {
        res.push_back(str);
        return;
    }

    // add left parentheses
    if (n1>0) {
        dfsParen(res, "("+leftStack, str+"(", n1-1, n2, n3);
    }
    if (n2>0) {
        dfsParen(res, "["+leftStack, str+"[", n1, n2-1, n3);
    }
    if (n3>0) {
        dfsParen(res, "{"+leftStack, str+"{", n1, n2, n3-1);
    }

    // add right parentheses
    if (!leftStack.empty()) {
        dfsParen(res, leftStack.substr(1), str+rightPart(leftStack.substr(0,1)), n1, n2, n3);
    }
}

vector<string> getParen(int n1, int n2, int n3) {
    vector<string> res;
    if (n1==0 && n2==0 && n3==0) return res;
    string leftStack;
    string str="";
    dfsParen(res, leftStack, str, n1, n2, n3);
    return res;
}

[LeetCode] String to Integer (atoi)

Problem Statement (link):

Implement atoi to convert a string to an integer.
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.

Analysis:
The logic/algorithm is pretty simple, the tricky part is about all the corner cases..:
1) "+-2" --> "0", multiple sign appeared;
2) Once you met a char, you should return the current integer by discarding all the rest of the string. i.e., "-23a56" --> "-23" rather than "-2356";
3) Overflow.

O(n) time complexity is required as we need to scan all the chars.

Code:

class Solution {
public:
    int atoi(const char *str) {
        while(*str==' ') str++;
        int sign=1;
        if (*str=='-' || *str=='+') {
            if ((*str=='+'&&*(str+1)=='-')||(*str=='-'&&*(str+1)=='+'))
                return 0;
            sign=*str=='-'?-1:1; str++;
        }

        int res=0;
        while(*str) {
            if (!isDigit(*str)) break;
            res=10*res+(*str-'0');
            str++;
            // overflow
            if ((res>=214748364 && *str>='8' && *str<='9') || res>=999999999 && isDigit(*str))
                return sign==1?INT_MAX:INT_MIN;
        }
        return res*sign;
    }
    bool isDigit(const char c) {
        int d=c-'0';
        if (d>=0 && d<=9)
            return true;
        return false;
    }
};

[LeetCode] Interleaving String

Problem Statement (link):

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Analysis:
It reminds me of the Edit Distance problem. As we could break this problem down to some smaller problems, i.e., consider if s1[:i-1] and s2[:j-1] could build s[:i+j-1], we could use DP.

We could construct a matrix dp[s1.length()+1][s2.length()+1], remember in DP we usually leave one more extra space for initial condition, which is both s1 and s2 are blank string in this problem. Each entry dp[i][j] indicates whether s1[i-1] and s2[j-1] could build  s[:i+j-1].

Now consider the transfer function. dp[i][j] is true if either of the following cases is true:
1) current char in s1 is same as current char in s3, and previous dp entry in the same row is true
i.e., s1[i-1]==s3[i+j-1] && dp[i-1][j]) == true
2) current char in s2 is same as current char in s3, and previous dp entry in the same col is true
i.e., s2[j-1]==s3[i+j-1] && dp[i][j-1] == true

Our final answer is in the last entry of the DP matrix.

The time complexity of the algorithm is O(len1 * len2), where the two lengths are the lengths of s1 and s2, respectively.

Code:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1=s1.length(), len2=s2.length();
        if (len1+len2!=s3.length()) return false;
        vector<vector<bool>> dp(len1+1, vector<bool> (len2+1, false));

        // initial
        dp[0][0]=true;
        for (int i=1; i<=len1; i++)
            if (s1[i-1]==s3[i-1] && dp[i-1][0]) dp[i][0]=true;
        for (int j=1; j<=len2; j++)
            if (s2[j-1]==s3[j-1] && dp[0][j-1]) dp[0][j]=true;

        // update dp
        for (int i=1; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                dp[i][j]=(s1[i-1]==s3[i+j-1] && dp[i-1][j]) || (s2[j-1]==s3[i+j-1] && dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
};

[LeetCode] Scramble String

Problem Statement (link):

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Analysis:
The problem nicely defined the scramble string as a node-swapped binary tree. Thus, we want to check any two siblings that if they are swapped.

Consider base cases:
For any string pairs, if they are of different size or consisted of different sets of letters, they are not scramble string. Further:
- If two string are the same, they are scramble string

Consider the recursion. Suppose we have the following two trees:

    node1
   /    \
left1   right1

    node2
   /    \
left2   right2

we will need to check isScramble(left1, left2) && isScramble(right1, right2), or isScramble(left1, right2) && isScramble(right1, left2), make sure the two strings passed in are the same length, as different-length strings are guaranteed to be non-Scramble.

The time complexity of this recursive algorithm is pretty high though in exponential. It gets pass the OJ because the conditions that I check before going to recursions.

In the worst situation, for any recursion f(n), we will check all the combinations twice, i.e., f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)], thus, f(n+1)=3*f(n), we have f(n)=3^n.

Code:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len=s1.size();
        if (s1==s2) return true;
        if (s1.size()!=s2.size()) return false;
        int val1=0, val2=0;
        for (int i=0; i<len; i++) {
            val1+=s1[i]-'a';
            val2+=s2[i]-'a';
        }
        if (val1!=val2) return false;
       
        for (int i=1; i<len; i++) {
            string a1=s1.substr(0,i);
            string b1=s1.substr(i);
            string a2=s2.substr(0,i);
            string b2=s2.substr(i);
            if (isScramble(a1,a2)&&isScramble(b1,b2))
                return true;
            string a3=s2.substr(len-i);
            string b3=s2.substr(0,len-i);
            if (isScramble(a1,a3)&&isScramble(b1,b3))
                return true;
        }
        return false;
    }
};

[LeetCode] Substring with Concatenation of All Words

Problem Statement (link):

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

Analysis:
The first solution I tried is to build a hash map that has all the combinations of words, so that we could have O(n/k) processing time afterwards, where n is the length of string S, and k is the length of a concatenated string. But I got MLE...

The second algorithm - see Sol 2 - , which is straightforward, got me an AC. Basically, we traverse the entire string S and check one word (NOT the concatenated long string!) at a time:
- if it matches our hash map, we check next word and so on;
- otherwise, we break immediately to check the word starts at next index

In the worst situation, where every time we check till the last word, we have O(n*m) time complexity, where n is the length of string S and m is the number of words in L.

Code:
Sol 1 - Memory Limit Exceed

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        unordered_set<string> comb; // store all combinations of L
        vector<int> res;
        string src="";
        for (int i=0; i<L.size(); i++) {
            src+=L[i];
        }

        // build up all permutations
        int match_len=L.size()*L[0].size();
        permute(comb, src, 0, match_len);

        // scan S
        for (int i=0; i<S.length(); i++) {
            if (i+match_len<S.length()) {
                string match_str=S.substr(i, match_len);
                if (comb.find(match_str)!=comb.end())
                    res.push_back(i);
            }
        }
        return res;
    }

    void permute(unordered_set<string> &comb, string &src, int st, int len) {
        if (st>=len-1) {
            comb.emplace(src);
            return;
        }
        for (int i=st; i<len; i+=3) {
            swap_words(src, st, i);
            permute(comb, src, st+3, len);
            swap_words(src, st, i);
        }
    }

    void swap_words(string &src, int a, int b) {
        string tmp_a=src.substr(a,3);
        string tmp_b=src.substr(b,3);
        for (int i=a; i<a+3; i++)
            src[i]=tmp_b[i-a];
        for (int i=b; i<b+3; i++)
            src[i]=tmp_a[i-b];
    }
};

Sol 2 - AC

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> res;
        unordered_map<string,int> map;
        for (int i=0; i<L.size(); i++)
            map[L[i]]++;

        // scan S
        int len=L[0].size();
        int match_len=L.size()*len;
        if (S.size()<match_len)
            return res;
        for (int i=0; i<=S.size()-match_len; i++) {
            unordered_map<string, int> map2;
            int j=0;
            for (j=0; j<match_len; j+=len) {
                string sub=S.substr(i+j, len);
                if (map.find(sub)!=map.end()) {
                    map2[sub]++;
                    if (map2[sub]>map[sub])
                        break;
                }
                else // immediately end loop
                    break;
            }
            // check if two map are the same
            if (j==match_len) res.push_back(i);
        }
        return res;
    }
};

[LeetCode] Longest Common Prefix

Problem Statement (link):
Write a function to find the longest common prefix string amongst an array of strings.
Analysis:
Pretty straight-forward. Choose any string, and compare its prefix - with length from 1 to the string length - with all other strings.

The time complexity is O(k*n), where k is the length of the string we choose, and n is the number of strings.

Code:

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        int size = strs.size();
        string result = "";
        if (size==0) return result;
        if (size==1) return strs.front();
        if (strs[0].empty()) return result;
       
        int len = strs[0].length();    // The longest prefix cannot be longer than any string, so take 1st string
        for (int k = 1; k <= len; k++) {     // k - length of current prefix
            string pref = strs[0].substr(0, k);
            for (int i = 1; i < size; i++) {// check thru all the strings in the vector, i - current string
                if (strs[i].empty()) return result;
                string pref_curr = strs[i].substr(0, k);
                if (pref.compare(pref_curr) != 0)   return pref.substr(0, k-1);
                if (k==len && i==size-1) return pref;
            }
        }
    }
};

[LeetCode] Next Permutation

Problem Statement (link):

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Analysis:
There's a classic algorithm on Wiki of finding the next string permutation in lexicographical order. There are four steps:
1) Find the largest index k where num[k]<num[k+1]
2) Find the largest index l where l>k and num[l]>num[k]
3) Swap num[k] and num[l]
4) Reverse num[k+1 : len], where len is the length of the given string

To see how this algorithm works, scratching a simple example on your own will help.

For our purpose, in addition to step 4, if there's no possible larger string found, we wrap up to find the smallest string by reversing the entire string.

Code:

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int len=num.size();
        if (len<=1) return;

        // step 1
        int k=0;
        for (int i=0; i<len-1; i++)
            if (num[i]<num[i+1])
                k=i;

        // step 2
        int l=0;
        for (int i=0; i<len; i++)
            if (i>k && num[k]<num[i])
                l=i;

        // step 3 - swap
        swap(num, k, l);

        //step 4 - reverse
        k==l ? reverse(num.begin(), num.end()):reverse(num.begin()+k+1, num.end());
    }
    void swap(vector<int> &num, int a, int b) {
        int t=num[a];
        num[a]=num[b];
        num[b]=t;
    }
};

[LeetCode] Count and Say

Problem Statement (link):

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.

Analysis:
No particular algorithms applied to this problem. Simply go through n rounds, wherein we calculate the time of each repeated characters and append to output string.

Code:

class Solution {
public:
    string countAndSay(int n) {
        string sout;
        string s="1";
        while(n-->1) {
            sout=helper(s);
            s=sout;
        }
        return s;
    }

    string helper(string s) {
        int count=0;
        char last=s[0];
        string sout="";
        for (int i=0; i<=s.length(); i++) {
            if (s[i]==last) count++;
            else {
                sout+=to_string(count)+s[i-1];
                last=s[i];
                count=1;
            }
        }
        return sout;
    }
};

[LeetCode] Minimum Window Substring

Problem Statement (link):

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.

Analysis:
We use two index pointers to maintain a sub-string window that contains the chars in T. Two hash tables are used, one contains all the chars in T as key field and their occurrences as value field; the other one is dynamic hash table that maintains chars in the sub-string window and their occurrences, these chars are only those appear in T. Further, an int is used to keep track of the number of matching chars in the sub-string window. This int is important as it closely associates with the movement of the two index pointers.

The pseudo-code goes like this:
Initialize parameters, two indexes == 0
Scan through T to update needtoFind hash table;
Start from the beginning of S, for each end value:
    if current char is not in T, continue;
    otherwise, add current char to hasFound hash table;
    if the occurrences of current char in hasFound is no larger than that in needtoFind, increase count;

    if count equals T size:
        if current char does not exist in T or its occurrences in hasFound is larger than that in needtoFind, we advance begin pointer, meanwhile, if current char exists in T and hasFound has larger occurrences, decrease the value in hasFound
        if current window is smaller, update the minimum string and its size

To better understand the algorithm, e.g., S = "DOBECAODEBAANC", T = "AABC", the red chars represent the dynamic window.

S	Variables
DOBECAODEBAANC	begin = 0, end = 0
DOBECAODEBAANC	begin = 0, end = 10	Advance end until find a match
DOBECAODEBAANC	begin = 5, end = 10	Advance begin
DOBECAODEBAANC	begin = 5, end = 11	count stays the same, advance end, increase hasFound['A']
DOBECAODEBAANC	begin = 5, end = 13	Advance end, increase hasFound['C']
DOBECAODEBAANC	begin = 6, end = 13	Advance begin, decrease hasFound['C']
DOBECAODEBAANC	begin = 9, end = 13	Advance begin, decrease hasFound['A']

Take-aways:
In C++11, we could manipulate the nonexistent keys in unordered_map directly without initialize that key value, and the initial value of that key is 0. For instance, the following code is legal:

unordered_map<char, int> map;
int val = map['a'];   // val==0
map['b']--;     // map['b']==-1
int sz = map.size();   // sz==2

Code:

class Solution {
public:
    string minWindow(string S, string T) {
        int begin=0, end=0;  // for scanning S
        int m=INT_MAX;  // min window size
        string ms="";      // min string
        int count=0;    // matching num of chars in current window

        unordered_map<char, int> hasFound;      // for string S
        unordered_map<char, int> needtoFind;    // for string T

        for (int i=0; i<T.size(); i++)
            needtoFind[T[i]]++;

        for (int end=0; end<S.size(); end++) {
            // skip chars not in T
            if (needtoFind.find(S[end])==needtoFind.end()) continue;
            // o.w. add char into hasFound table
            hasFound[S[end]]++;
            if (hasFound[S[end]] <= needtoFind[S[end]]) count++;

            if (count==T.size()) {
                // advance begin pointer
                while (needtoFind.find(S[begin])==needtoFind.end() || hasFound[S[begin]]>needtoFind[S[begin]]) {
                    if (needtoFind.find(S[begin])!=needtoFind.end() && hasFound[S[begin]]>needtoFind[S[begin]]) hasFound[S[begin]]--;
                    begin++;
                }

                // update min string
                int winLen=end-begin+1;
                if (winLen<m) {
                    m=winLen;
                    ms=S.substr(begin, winLen);
                }
            }
        }
        return ms;
    }
};

[LeetCode] Add Binary

Problem Statement (link):

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

Analysis:
Starting from end of strings, we add corresponding two digits together. Need to consider the followings:

1) a variable to record if there's carry in each addition;
2) if there's carry when we reach the MSB of two binaries, need to append another digit 1 in front;
3) (option) we could add dummy '0's in front of the shorter string, such that the code is cleaner and easier to understand.

Code:

class Solution {
public:
    string addBinary(string a, string b) {
        string c="";
        int carry=0;
        int al=a.size(), bl=b.size();
        int cl=max(al, bl);

        for (int i=0; i<cl; i++){
            // add dummy 0s in front of shorter string
            int k1=i<al ? a[al-i-1]-'0':0;
            int k2=i<bl ? b[bl-i-1]-'0':0;
            c=to_string((k1+k2+carry)%2)+c;
            carry=(k1+k2+carry)/2;
        }

        // need to check the last carry
        return carry==1 ? "1"+c:c;
    }
};

[LeetCode] Anagrams

Problem Statement (link):

Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

Analysis:
How to determine if two strings are anagrams?

My first thought was to store each chars from the first string in a hash map, then probe the hash map with each chars in the second string to determine if two strings have the sames chars. If we use this approach, we need to make sure we consider the duplication cases. We could potentially use the value field in the hash map to record the number of occurrence of each char. The time complexity is O(m), where m is the length of the string. The implementation is provided at the end of this post

The second idea is to simply sort string 1, and compare it with the sorted string 2, if they are equal, it means these two are anagrams. The time complexity of this algorithm is O(m log m), which is worse than the first one where we use hash map. However, it turned out that this idea suits this problem better as we have to probe another hash map that stores all strings every time a new string comes in in order to determine if the incoming string is anagram with any of the existing strings in the hash map, this leads to a O(m*n^2) algorithm in general.

The overall time complexity of the second approach is O(n * m log m). Where n is the number of strings and m is the average string length.

Code:

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> out;
        if (strs.empty()) return out;
        unordered_map<string, int> map;

        for (int i=0; i<strs.size(); i++) {
            string tmp=strs[i];
            sort(tmp.begin(), tmp.end());

            if (map.find(tmp)!=map.end()) { // found
                out.push_back(strs[i]);
                // insert the 1st occurance string if hvn't done it
                if (map[tmp]>=0) { 
                    out.push_back(strs[map[tmp]]);
                    map[tmp]=-1;
                }
            }
            else
                map.emplace(tmp, i);
        }
        return out;
    }
};

Takeaways:
- A better partial solution doesn't necessarily lead to a better overall solution.

Here is the code for checking if two strings are anagrams using a hash map, assuming the strings are legal.

bool isAnagram(string a, string b) {
    unordered_map<char, int> map;

    // construct map using string a
    for (int i=0; i<a.size(); i++) {
        if (map.find(a[i]) == map.end())
            map.emplace(a[i], 1);
        else
            map[a[i]]++;
    }

    // check anagram using the map
    for (int i=0; i<b.size(); i++) {
        if (map.find(b[i])==map.end() || map[b[i]]<1)
            return false;
        else
            map[b[i]]--;
    }

    // check map if all value is 0
    for (unordered_map<char, int>::iterator it=map.begin(); it!=map.end(); it++)
        if (it->second!=0)
            return false;
    return true;
}

[LeetCode] Implement strStr()

Problem Statement (link)

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Analysis:
No specific algorithm needed for this problem. We simply traverse the two strings and compare each char. The time complexity is O(n*m), where n and m are the lengths of string needle and string haystack, respectively.

Code:

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        char *st=haystack;
        char *pt1=haystack;
        char *pt2=needle;

        while(*pt1!=NULL && *pt2!=NULL) {
            if (*pt1==*pt2) {
                pt1++; pt2++;
                continue;
            }
            st++;
            pt1=st;
            pt2=needle;
        }
        return *pt2==NULL ? st:NULL;
    }
};

[LeetCode] Valid Palindrome

Problem Statement (link):

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

Analysis:
We compare the to chars from head and tail of the string, if they are the same, we proceed on checking the next char pair, otherwise, we return false.

Note that we need to check if the chars are valid chars before comparison.

This algorithm gives us O(n) time complexity.

Code:

class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty()) return true;
        int len=s.length();
       
        int head=0, tail=len-1;
        while (tail>=head) {
            // Skip invalid chars
            if (!isValid(s[head])) {
                head++;
                continue;
            }
            if (!isValid(s[tail])) {
                tail--;
                continue;
            }

            if (!isEqual(s[head], s[tail])) return false;
            head++; tail--;
        }
        return true;
    }
       
    bool isEqual(char c1, char c2) {
        if (c1==c2 || c1-c2=='A'-'a' || c1-c2=='a'-'A')
            return true;
        return false;
    }
    bool isValid(char c1) {
        if ((c1-'0'>=0 && c1-'0'<10) || (c1-'a'>=0 && c1-'a'< 26) || (c1-'A'>=0 && c1-'A'<26))
            return true;
        return false;
    }
};

[LeetCode] Restore IP Address

Problem Statement (link):

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Analysis:
There's no specific algorithm used in this problem. I loop through all the possible positions to add dots.

A value IP address is defined such that each three-digits segment is valued between 0 and 255, inclusive. A corner case is that each segment should begin with non-zero digits, i.e., xx.013.xxx.xxx is not a valid segmentation as 013 is invalid.

Code:

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> out;
        if (s.size()<4 || s.size()>12) return out;
        // loop thru all possible positions for adding "."
        for (int i=0; i<s.size()-3; i++) {
            for (int j=i+1; j<s.size()-2; j++) {
                for (int k=j+1; k<s.size()-1; k++) {
                    int a=atoi(s.substr(0,i+1).c_str());
                    string t=to_string(a);
                    if (t!=s.substr(0,i+1)) continue; // to eliminate case where starts with 0

                    int b=atoi(s.substr(i+1,j-i).c_str());
                    t=to_string(b);
                    if (t!=s.substr(i+1,j-i)) continue;

                    int c=atoi(s.substr(j+1,k-j).c_str());
                    t=to_string(c);
                    if (t!=s.substr(j+1,k-j)) continue;

                    int d=atoi(s.substr(k+1,s.size()-k).c_str());
                    t=to_string(d);
                    if (t!=s.substr(k+1,s.size()-k)) continue;

                    if (a<=255 && b<=255 && c<=255 && d<=255)
                        out.push_back(s.substr(0,i+1)+"."+s.substr(i+1,j-i)+"."+s.substr(j+1,k-j)+"."+s.substr(k+1,s.size()-k));
                }
            }
        }
        return out;
    }
};

[LeetCode] Length of Last Word

Problem Statement (link):

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.

Analysis:
- Just traverse the char array until you hit NULL.
- Remember to reset the count once you hit a space char, iff it's not the last word.
- The logic I use to determine that it is NOT the last word, where we need to reset the count, is: 1) If current char is space char; 2) If the next char is not space char; 3) If the next char is not NULL.

e.g., string: "ab     cde    "

where we need to reset count when we hit the space before c, we shouldn't reset count when we hit spaces after e.

Code:

class Solution {
public:
    int lengthOfLastWord(const char *s) {
        if (*s==NULL) return 0;
        int len=0;
        const char *cur=s;

        while(*cur!=NULL) {
            if (*cur!=' ')
                len++;
            if (*cur==' ' && *(cur+1)!=' ' && *(cur+1)!=NULL) // if there is a next word
                    len=0;
            cur++;
        }
        return len;
    }
};

[LeetCode] Roman to Interger

Problem Statement (link):

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

Analysis:
There isn't so much to say about this problem. Just adding the number together. When the number current char represents is smaller than that of the next char, to calculate the number that these two chars represent, you need to subtract the number that current char represents from that of the next char. e.g., XXIX, the first two X represent 10+10, the next IX represent 10-1, thus the result is 10+10+(10-1)=29.

A comprehensive description of the rules of Roman Numeral is here. Unfortunately, the link is Chinese.

Code:

class Solution {
public:
    int romanToInt(string s) {
        if (s.empty()) return 0;
        int out=0, i=0;
        while (i<s.size()) {
            if (i+1<s.size() && helper(s[i])<helper(s[i+1])) { // the next char exists and it's greater than curr
                out+=helper(s[i+1])-helper(s[i]);
                i++;
            }
            else
                out+=helper(s[i]);
            i++;
        }
        return out;
    }

    int helper(char c) {
        int num=0;
        switch(c) {
            case 'I':
                num=1;
                break;
            case 'V':
                num=5;
                break;
            case 'X':
                num=10;
                break;
            case 'L':
                num=50;
                break;
            case 'C':
                num=100;
                break;
            case 'D':
                num=500;
                break;
            case 'M':
                num=1000;
                break;
            default:
                num=0;
                break;
        }
        return num;
    }
};

[LeetCode] Longest Substring Without Repeating Characters

Problem Statement (link):
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.

Analysis:
The algorithm is straightforward. We start at the beginning of the string s, for char s[i], we find the longest substr, and move on to the next char s[i+1], repeat.

The interesting part is to choose the best data structure to store the substr's each char as we do need to compare the new char with chars we've seen. I chose unordered_map<string, int> to store and hope the hash map could give me O(1) access each time. I passed all the tests months ago, but now I re-submit the solution, it notified TLE for a rather long string. Apparently, there's collision that drove the complexity beyond O(n), where n is the string length.

Another data structure that fits this problem is array, which provides us O(1) access time. Also, remember that ASCII chars are indexed from 0 to 127. Thus, we could match the ASCII index for each char with our array map, which indicates if we have seen the char before.

Code:
Sol 1: Use unordered_map<string, int>

int lengthOfLongestSubstring(string s) {
    if (s.compare("")==0) return 0;
    int len = s.size();
    int maxLength = 1;
    unordered_map<string, int> table;
    int i = 0;
    while (i<len) {
        table.emplace(s.substr(i,1), i);  // i is the char's location
        for (int j = 1; j < len-i; j++) { // represent the length
            if (table.find(s.substr(i+j, 1)) != table.end()) {   // found the same char, break
                i=table.find(s.substr(i+j,1))->second;
                table.clear();
                break;
            }
            else { // not found - update max length
                maxLength=max(maxLength, j+1);
                table.emplace(s.substr(i+j, 1), i+j);
            }
       }
       i++;
    }
    return maxLength;
}

Sol 2: Use bool arr[128]

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        int len=s.size();
        int maxLen=1;
        int i=0;
        while (i<len) {
            bool arr[128]={false}; // to record if any char appeared in ASCII, Unicode has 256 chars
            arr[s[i]]=true;
            for (int j=1; j<len-i; j++) {
                if (arr[s[i+j]]==true) { // found same char
                    break;
                }
                else {
                    maxLen=max(maxLen,j+1);
                    arr[s[i+j]]=true;
                }
            }
            i++;
        }
        return maxLen;
    }
};

Takeaways:
- hash based data structure cannot guarantee O(1) access. If possible, think about using other O(1) structure instead.

[LeetCode] Word Break II

Problem Statement (link):

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

Analysis:
This problem requires us to return all the possible combinations with dictionary words.

The first idea is to implement a recursive DFS algorithm. In which, consider each possible prefix as a node in a n-nary tree, where n is the possible word choices starting from next index. For example, in the given example, if we construct a tree like:

                                                              ""               --> NULL string as root node
                                                          /        \
                                                   "cat"         "cats"
                                                      /                \
                                             "sand"                "and"    
                                                  /                        \
                                           "dog"                       "dog"

At each node, we need to search the entire dictionary for next possible word (child nodes).

The time complexity of this algorithm is O(m*n^2) in worst case, where n is length of string s, and m is the length of the dictionary.

I implemented this algorithm in Sol 1. However, it got TLE from OJ. How come?

If we look into the algorithm carefully, we could see there are two places that we may improve:
1) Dictionary look up duplication. In the given example, we could see that the two nodes "dog" at the last level are same. However, the DFS will do a dictionary scan each time;
2) Un-necessary look up. Suppose we had a string/sub-string s = "Leetcode", even if dictionary has no word "L" or words starting with "L", the algorithm will search next letter "e" as well.

We could borrow the DP idea from Word Break I to improve the 2) problem, where dp[i] indicates if s[i : n-1] could be constructed by dictionary words. If not, we stop search search immediately and move on. This idea is called backtracking, the dp vector here serves as the stop condition in backtracking.

The dp index map is as follows:

string:         c  a  t  s  a  n  d  d  o  g
i:                 0  1  2  3  4  5  6  7  8  9
dp:              0  1  2  3  4  5  6  7  8  9  10 --> dp[10]==true serving as the initial condition

However, I was not able to solve 1) problem.

To sum up, the time complexity of the improved algorithm is still O(m*n^2), but it saves a lot of time by stop searching earlier according to the pre-constructed dp vector.

Code:
Sol 1 - Recursive DFS:

vector<string> wordBreak(string s, unordered_set<string> &dict) {
    vector<string> dp;  // Store the out sequence
    recur(dict, dp, s, "");
    return dp;
}
void recur(unordered_set<string>& dict, vector<string>& dp, string s, string res){
    for (int i=1; i<=s.length(); i++){   // length of prefix
        if (dict.find(s.substr(0, i))!=dict.end()) {
            if (i==s.length()) {
                res+=s.substr(0, i);
                dp.push_back(res);
                return;
            }
            recur(dict, dp, s.substr(i, s.length()-i), res+s.substr(0,i)+" ");
        }
    }
    return;
}

Sol 2 - DFS + Backtracking (realized by DP):

class Solution {
public:
    // recursion + dp
    vector<string> wordBreak(string s, unordered_set<string> &dict){
        int len = s.length();
        vector<string> out;
        vector<bool> dp(len+1, false);
        // indicates if s[i, n-1] can be represented by dict
        dp[len]=true;
        for (int i=len-1; i>=0; i--) {
            if (dict.find(s.substr(i, len))!=dict.end()) {
                dp[i]=true;
                continue;
            }
            for (int j=i+1; j<len; j++) {
                if (dp[j]==true && dict.find(s.substr(i,j-i))!=dict.end()) {
                    dp[i]=true;
                }
            }
        }
        // dp + recursion
        recur(dict, dp, out, s, "", 0);
        return out;
    }

    // st-current substr start index
    void recur(unordered_set<string>& dict, vector<bool>& dp, vector<string>& out, string s, string res, int st) {
        for (int i=1; i<=s.length(); i++) {
            if (dict.find(s.substr(0, i))!=dict.end() && dp[st]==true) {
                if (i==s.length()) {
                    res+=s.substr(0, i);
                    out.push_back(res);
                    return;
                }
                recur(dict, dp, out, s.substr(i,s.length()-i), res+s.substr(0, i)+" ", st+i);
            }
        }
    }
}

Take-aways:
- Consider DFS when asked to "find all", "return all possible".
- Consider backtracking to save time - what would be the stop condition?