408. Valid Word Abbreviation

No trick. Pretty straightforward solution. Note when return, we need to check if we've reached both ends of word and it abbreviation.

1:  class Solution {  
2:  public:  
3:    bool validWordAbbreviation(string word, string abbr) {  
4:      int i = 0, j = 0;  
5:      while (i < word.size() && j < abbr.size()) {  
6:        if (!isNum(abbr[j])) {  
7:          if (word[i++] != abbr[j++]) return false;  
8:        } else {  
9:          if (abbr[j] == '0') return false;  
10:          int l = 0;  
11:          while (j < abbr.size() && isNum(abbr[j])) {  
12:            l = l * 10 + abbr[j++] - '0';  
13:          }  
14:          i += l;  
15:        }  
16:      }  
17:      return i == word.size() && j == abbr.size();  
18:    }  
19:    bool isNum(char c) {  
20:      return c >= '0' && c <= '9';  
21:    }  
22:  };  

394. Decode String

One way to solve the problem is DFS. But the trick is the input index. The index must be reference (or pointer) because it should be continuous to the function call in the stack.

1:  class Solution {  
2:  public:  
3:    string decodeString(string s) {  
4:      int i = 0;  
5:      return helper(s, i);  
6:    }  
7:    string helper(string s, int &i) {  
8:      string res;  
9:      while (i < s.size() && s[i] != ']') {  
10:        if (!isDigit(s[i])) res += s[i++];  
11:        else {  
12:          int n = 0;  
13:          while (i < s.size() && isDigit(s[i])) n = n * 10 + s[i++] - '0';  
14:          i++; // '['  
15:          string t = helper(s, i);  
16:          i++; // ']'  
17:          for (int j = 0; j < n; j++) res += t;  
18:        }  
19:      }  
20:      return res;  
21:    }  
22:    bool isDigit(char c) {  
23:      return c >= '0' && c <= '9';  
24:    }  
25:  };  

388. Longest Absolute File Path

This problem has long long description and the file path is very confusing at the first glance. However, if you read the path carefully, you'll find that '\t' indicates the depth of a directory or file and '\n' indicates the end of the directory or file. Also you should notice that the file in the path appears one by one, so the solution becomes to have an array to store the length for each depth and once reaches a file, compute the total length to the file. After computing a file, everything can be reset to start finding a new file.

1:  class Solution {  
2:  public:  
3:    int lengthLongestPath(string input) {  
4:      int maxL = 0, l = 1, len = 0;  
5:      bool isFile = false;  
6:      vector<int> level(1, 0);  
7:      for (int i = 0; i < input.size(); i++) {  
8:        while (input[i] == '\t') {  
9:          l++, i++;  
10:        }  
11:        while (input[i] != '\n' && i < input.size()) {  
12:          if (input[i] == '.') isFile = true;  
13:          len++, i++;  
14:        }  
15:        if (isFile) {  
16:          maxL = max(maxL, level[l-1]+len);  
17:        } else {  
18:          if (l == level.size()) level.push_back(level[l-1]+len+1);  
19:          else level[l] = level[l-1] + len + 1;  
20:        }  
21:        len = 0, l = 1, isFile = false;  
22:      }  
23:      return maxL;  
24:    }  
25:  };  

67. Add Binary

Very straightforward solution. I think the little challenge is the make the code clean and clever.

1:  class Solution {  
2:  public:  
3:    string addBinary(string a, string b) {  
4:      string s = "";  
5:      int c = 0, i = a.size()-1, j = b.size()-1;  
6:      while (i >= 0 || j >= 0 || c == 1) {  
7:        c += i >= 0 ? a[i--] - '0' : 0;  
8:        c += j >= 0 ? b[j--] - '0' : 0;  
9:        char t = c % 2 + '0';  
10:        s = t + s;  
11:        c /= 2;  
12:      }  
13:      return s;  
14:    }  
15:  };  

161. One Edit Distance

I was thinking of DP, but it turns out quite straightforward. See the comments in the code.

1:  class Solution {  
2:  public:  
3:    bool isOneEditDistance(string s, string t) {  
4:      int ns = s.size();  
5:      int nt = t.size();  
6:      int n = min(ns, nt);  
7:      for (int i = 0; i < n; i++) {  
8:        if (s[i] != t[i]) {  
9:          if (ns == nt) return s.substr(i+1) == t.substr(i+1); // replace s[i] with t[i]  
10:          else if (ns < nt) return s.substr(i) == t.substr(i+1); // delete t[i]  
11:          else return s.substr(i+1) == t.substr(i); // delete s[i]  
12:        }  
13:      }  
14:      return abs(ns-nt) == 1; // one character long otherwise two strings are equal.  
15:    }  
16:  };  

227. Basic Calculator II

The difference with problem "224. Basic Calculator" is that this problem contains '*' and '/' operator but no parenthesis. We can use stack to solve this problem. Stack stores all the numbers that need to sum up. So when we meet '+', we simply push the number into stack. When we meet '-', we simply push the negative number into the stack. When we meet '*' or '/' which has high priority, we only need to pop the top number out of the stack, operate on it and push it back to stack. With this operation, the stack will store all the numbers that need to sum up only.

1:  class Solution {  
2:  public:  
3:    int calculate(string s) {  
4:      char sign = '+';  
5:      int num = 0;  
6:      stack<int> stk;  
7:      for (int i = 0; i < s.size(); i++) {  
8:        if (s[i] >= '0' && s[i] <= '9') {  
9:          num = num*10+s[i]-'0';  
10:        }  
11:        if (((s[i] < '0' || s[i] > '9') && (s[i] != ' ')) || i == s.size()-1) {  
12:          if (sign == '+') stk.push(num);  
13:          else if (sign == '-') stk.push(-num);  
14:          else if (sign == '*') {num *= stk.top(); stk.pop(); stk.push(num);}  
15:          else if (sign == '/') {num = stk.top()/num; stk.pop(); stk.push(num);}  
16:          sign = s[i];  
17:          num = 0;  
18:        }  
19:      }  
20:      int res = 0;  
21:      while (!stk.empty()) {  
22:        res += stk.top();  
23:        stk.pop();  
24:      }  
25:      return res;  
26:    }  
27:  };  

71. Simplify Path

I don't have a clue in first place. But after looking at the tag "stack", then I got an idea. We can store each directory into a stack. Then I'll have following case:

1. directory is empty (i.e. consecutive slashes "///")or directory is ".", then we don't have to do anything.
2. directory is "..", then we need to pop out one directory. Note we need to check the stack is empty or not. If it's empty, we don't have to do anything.
3. Otherwise, we push the directory into the stack.

Since we eventually need to pop out the directories to form a new path but the stack is in reverse order, so we can use a vector to replace the stack so that we can traverse the vector from the beginning to the end.

1:  class Solution {  
2:  public:  
3:    string simplifyPath(string path) {  
4:      vector<string> dirs;  
5:      int i = 0, j = 0;  
6:      while (i < path.size()) {  
7:        while (i < path.size() && path[i] != '/') i++;  
8:        string dir = path.substr(j, i-j);  
9:        j = ++i;  
10:        if (dir == "" || dir == ".") continue;  
11:        if (dir == ".." && !dirs.empty()) dirs.pop_back();  
12:        else if (dir != "..") dirs.push_back(dir);  
13:      }  
14:      string res;  
15:      for (int i = 0; i < dirs.size(); i++) {  
16:        res += "/" + dirs[i];  
17:      }  
18:      return res.empty() ? "/" : res;  
19:    }  
20:  };  

186. Reverse Words in a String II

This is similar to problem "151. Reverse Words in a String". The idea is the same, i.e. reverse all the string first and reverse each word in the string.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      reverse(s.begin(), s.end());  
5:      int i = 0, j = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && s[i] != ' ') i++;  
8:        reverse(s.begin()+j, s.begin()+i);  
9:        j = ++i;  
10:      }  
11:    }  
12:  };  

8. String to Integer (atoi)

This is "easy" for programming if you are clear about all possible cases. Need to get the requirment clarified from the interviewer. Anyway, here are the cases that OJ thinks of (I've added comments for the cases in the code).

1:  class Solution {  
2:  public:  
3:    int myAtoi(string str) {  
4:      int i = 0, n = str.size();  
5:      long long res = 0;  
6:      int sign = 1;  
7:      // ignore leading spaces  
8:      while (str[i] == ' ') i++;  
9:      // process leading sign  
10:      if (str[i] == '-') { sign = -1; i++; }  
11:      else if (str[i] == '+') { sign = 1; i++; }  
12:      while (i < n && isNum(str[i])) {  
13:        res = res*10 + str[i]-'0';  
14:        // process overflow;  
15:        if (sign == 1 && res > INT_MAX) return INT_MAX;  
16:        if (sign == -1 && -res < INT_MIN) return INT_MIN;  
17:        i++;  
18:      }  
19:      return res * sign;  
20:    }  
21:    bool isNum(char c) {  
22:      return c >= '0' && c <= '9';  
23:    }  
24:  };  

3. Longest Substring Without Repeating Characters

This is very similar idea to problem "340. Longest Substring with At Most K Distinct Characters".
1. we keep moving one pointer and count each character until one character has been counted before, i.e. the count for the character is one already.
2. Then we move another pointer and decrease the counter for each character until the character pointed by the first pointer has count 0.
3. And then leave the second pointer there and move the first pointer again. Repeat step 1-2 until the first pointer reaches the end.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstring(string s) {  
4:      vector<int> chars(256, 0);  
5:      int i = 0, j = 0, maxLen = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && chars[s[i]] == 0) {++chars[s[i++]];};  
8:        maxLen = max(maxLen, i - j);  
9:        while (i < s.size() && chars[s[i]] == 1) --chars[s[j++]];  
10:      }  
11:      return maxLen;  
12:    }  
13:  };  

126. Word Ladder II

I built my solution on top of problem 127 "Word Ladder". I use a hash map to store the prior string set of current string. The key is current string and the value is the prior string set. The reason I use unordered_set for prior strings is to avoid duplicates. The basic idea is to find the shortest transformation sequence first and then build the sequences by the hash map.

1:  class Solution {  
2:  private:  
3:    unordered_map<string, unordered_set<string>> mp;  
4:    queue<string> q;  
5:    vector<vector<string>> res;  
6:    vector<string> path;  
7:    int dist;  
8:  public:  
9:    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
10:      dist = helper(start, end, dict);  
11:      if (dist) output(start, end);  
12:      return res;   
13:    }  
14:    int helper(string &start, string &end, unordered_set<string> &dict) {  
15:      dict.insert(start);  
16:      q.push(start);  
17:      path.push_back(end);  
18:      dist = 1;  
19:      while (!q.empty()) {  
20:        int n = q.size();  
21:        for (int i = 0; i < n; i++) {  
22:          dict.erase(q.front());  
23:          q.push(q.front());  
24:          q.pop();  
25:        }  
26:        for (int i = 0; i < n; i++) {  
27:          string word = q.front();  
28:          q.pop();  
29:          if (word == end) return dist;  
30:          addNeighbors(word, dict);  
31:        }  
32:        dist++;  
33:      }  
34:      return 0;  
35:    }  
36:    void addNeighbors(string word, unordered_set<string> &dict) {  
37:      string tmp = word;  
38:      for (int i = 0; i < word.size(); i++) {  
39:        char c = tmp[i];  
40:        for (int j = 0; j < 26; j++) {  
41:          tmp[i] = 'a' + j;  
42:          if (dict.count(tmp)) {  
43:            q.push(tmp);  
44:            mp[tmp].insert(word);  
45:          }  
46:        }  
47:        tmp[i] = c;  
48:      }  
49:    }  
50:    void output(string &start, string end) {  
51:      if (path.size() == dist) {  
52:        if (start == end) {  
53:          reverse(path.begin(), path.end());  
54:          res.push_back(path);  
55:          reverse(path.begin(), path.end());  
56:        }  
57:        return;  
58:      }  
59:      int n = mp[end].size();  
60:      for (auto it = mp[end].begin(); it != mp[end].end(); it++) {  
61:        string s = *it;  
62:        path.push_back(s);  
63:        output(start, s);  
64:        path.pop_back();  
65:      }  
66:    }  
67:  };  

214. Shortest Palindrome

I have to follow the top rated solution. The top one uses the KMP algorithm.
Here are two good links explaining this algorithm.
https://www.youtube.com/watch?v=GTJr8OvyEVQ
https://www.youtube.com/watch?v=KG44VoDtsAA
After preprocessing the pattern, the kmp[i] is the longest length of the suffix that matches prefix at ith character in pattern string. So if we concatenate input string s and its reversed string r, and process the concatenated string by KMP algorithm, we know that the longest length that the suffix of string r matches prefix of string s is kmp[kmp.size()-1]. Let’s take “aacecaaa” as an example here.
The concatenated string will be “aacecaaa#aaacecaa” (Why put # here? I’ll explain later)
After KMP processing, the kmp vector will be [0 1 0 0 0 1 2 2 0 1 2 2 3 4 5 6 7]. So for the last character, the longest length that the suffix matches prefix is 7. Note the suffix of the string is actually the reversed input string and the prefix is the input string itself. Also, it means that there is already 7 characters from the beginning matches the 7 characters that from the end. So all we need to do is to copy the rest 1 unmatched character to the beginning of the input string in a reverse order, which is exactly copying the first 1 character in the reversed string to the beginning of the input string.

When I revisited this problem, I made mistake in
line 16: I was checking "j != 0". However, we should check "tmp[i] == tmp[j]" because even j reaches back to 0, it's still possible that "tmp[i] == tmp[j]" and thus kmp[i] should be 1 not 0.

1:  class Solution {  
2:  public:  
3:    string shortestPalindrome(string s) {  
4:      string r = s;  
5:      reverse(r.begin(), r.end());  
6:      string tmp = s + "#" + r;  
7:      vector<int> kmp(tmp.size(), 0);  
8:      int i = 1, j = 0;  
9:      for (; i < tmp.size(); i++) {  
10:        if (tmp[i] == tmp[j]) kmp[i] = ++j;  
11:        else {  
12:          j = kmp[j-1];  
13:          while (j > 0 && tmp[i] != tmp[j]) {  
14:            j = kmp[j-1];  
15:          }  
16:          if (tmp[i] == tmp[j]) {  
17:            kmp[i] = j+1;  
18:            j++;  
19:          }  
20:        }  
21:      }  
22:      return r.substr(0, s.size()-kmp[kmp.size()-1])+s;  
23:    }  
24:  };  

Now let’s look at why “#” is needed. Without “#”, what happens if the input string is “aa”? The kmp vector will be [0 1 2 3]. The kmp[kmp.size()-1] is larger than the input string size which makes return line invalid.
And here is a short version of KMP algorithm.

1:  class Solution {  
2:  public:  
3:    string shortestPalindrome(string s) {  
4:      string r = s;  
5:      reverse(r.begin(), r.end());  
6:      string tmp = s + "#" + r;  
7:      vector<int> kmp(tmp.size(), 0);  
8:      int i = 1, j = 0;  
9:      for (; i < tmp.size(); i++) {  
10:        j = kmp[i-1];  
11:        while (j > 0 && tmp[i] != tmp[j]) {  
12:          j = kmp[j-1];  
13:        }  
14:        kmp[i] = (j += tmp[i] == tmp[j]);  
15:      }  
16:      return r.substr(0, s.size()-kmp[kmp.size()-1])+s;  
17:    }  
18:  };  

17. Letter Combinations of a Phone Number

A typical backtracking solution.

1:  class Solution {  
2:  private:  
3:    vector<string> pad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
4:  public:  
5:    vector<string> letterCombinations(string digits) {  
6:      vector<string> res;  
7:      if (digits.size() == 0) return res;  
8:      helper(digits, 0, "", res);  
9:      return res;  
10:    }  
11:    void helper(string &digits, int i, string sol, vector<string> &res) {  
12:      if (i == digits.size()) {  
13:        res.push_back(sol); return;  
14:      }  
15:      for (int j = 0; j < pad[digits[i]-'0'].size(); j++) {  
16:        sol += pad[digits[i]-'0'][j];  
17:        helper(digits, i+1, sol, res);  
18:        sol.pop_back();  
19:      }  
20:    }  
21:  };  

345. Reverse Vowels of a String

Easy, but easy to make mistake. I've highlighted in red the mistakes I made.

1:  class Solution {  
2:  public:  
3:    string reverseVowels(string s) {  
4:      if (s.empty()) return s;  
5:      int i = 0, j = s.size() - 1;  
6:      while (i < j) {  
7:        while (i < j && !isVowel(s[i])) i++;  
8:        while (i < j && !isVowel(s[j])) j--;  
9:        swap(s[i], s[j]);  
10:        i++, j--;  
11:      }  
12:      return s;  
13:    }  
14:    bool isVowel(char c) {  
15:      c = tolower(c);  
16:      return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';  
17:    }  
18:  };  

293. Flip Game

Well, an easy one.

1:  class Solution {  
2:  public:  
3:    vector<string> generatePossibleNextMoves(string s) {  
4:      int n = s.size();  
5:      vector<string> res;  
6:      for (int i = 0; i < n-1; i++) {  
7:        if (s[i] == '+' && s[i+1] == '+') {  
8:          s[i] = s[i+1] = '-';  
9:          res.push_back(s);  
10:          s[i] = s[i+1] = '+';  
11:        }  
12:      }  
13:      return res;  
14:    }  
15:  };  

271. Encode and Decode Strings

The idea is easy. To have a fixed length header to contain the length of the string. When decode, parse the header and get the string whose length is specified by the header.

When I revisited this problem, I made mistake in
line 9: I mistakenly had "res += to_string(strs[i].size()) + string(HEAD_SIZE-strs[i].size(), '.' + strs[i]". Note, the head size should be the size of the converted head size number.
line 17: I mistakenly had "i++" in the end.

1:  #define HEAD_SIZE 16  
2:  class Codec {  
3:  public:  
4:    // Encodes a list of strings to a single string.  
5:    string encode(vector<string>& strs) {  
6:      string res;  
7:      for (int i = 0; i < strs.size(); i++) {  
8:        string s = to_string(strs[i].size());  
9:        string append = string(HEAD_SIZE-s.size(), '.');  
10:        res += s + append + strs[i];  
11:      }  
12:      return res;  
13:    }  
14:    // Decodes a single string to a list of strings.  
15:    vector<string> decode(string s) {  
16:      vector<string> res;  
17:      for (int i = 0; i < s.size();) {  
18:        string head = s.substr(i, HEAD_SIZE);  
19:        int len = stol(head, NULL, 10);  
20:        i += HEAD_SIZE;  
21:        if (len > 0) res.push_back(s.substr(i, len));  
22:        else res.push_back("");  
23:        i += len;  
24:      }  
25:      return res;  
26:    }  
27:  };  
28:  // Your Codec object will be instantiated and called as such:  
29:  // Codec codec;  
30:  // codec.decode(codec.encode(strs));  

340. Longest Substring with At Most K Distinct Characters

I implemented a naive code first. And of course, it doesn’t pass large test set.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringKDistinct(string s, int k) {  
4:      if (s.size() < k) return s.size();  
5:      int res = 0;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        vector<int> letters(256, 0);  
8:        int count = 0;  
9:        int j = i;  
10:        while (j < s.size()) {  
11:          if (letters[s[j]] == 0) {  
12:            letters[s[j]] = 1;  
13:            count++;  
14:            if (count > k) break;  
15:          }  
16:          j++;  
17:        }  
18:        res = max(res, j-i);  
19:      }  
20:      return res;  
21:    }  
22:  };  

The top rated solution uses sliding window. Keep two pointers as the starting of the window and the end of the window. First of all, keep moving the right end of the window until the distinct characters are more than K. Then move the left end of the window until the distinct characters are equal to K. Then move right end again.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringKDistinct(string s, int k) {  
4:      int res = 0, j = -1, i = 0, distinct = 0;  
5:      vector<int> chars(256, 0);  
6:      for (; i < s.size(); i++) {  
7:        distinct += chars[s[i]]++ == 0;  
8:        while (distinct > k) {  
9:          distinct -= --chars[s[++j]] == 0;  
10:        }  
11:        res = max(res, i-j);  
12:      }  
13:      return res;  
14:    }  
15:  };  

159. Longest Substring with At Most Two Distinct Characters

Same as problem “340. Longest Substring with At Most K Distinct Characters”.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringTwoDistinct(string s) {  
4:      int i = 0, j = -1;  
5:      vector<int> dict(256, 0);  
6:      int len = 0;  
7:      int k = 0;  
8:      while (i < s.size()) {  
9:        k += dict[s[i]]++ == 0;  
10:        while (k > 2) k -= --dict[s[++j]] == 0;  
11:        len = max(len, i-j);  
12:        i++;  
13:      }  
14:      return len;  
15:    }  
16:  };  

249. Group Shifted Strings

The intuition is to create a pattern for each string and use the pattern as key in hash table. The value is a string vector that contains all strings follow the same pattern. Then the problem becomes how to create the pattern. The naive way is to use "a" + diff. Since the diff can be negative (e.g. "ba" and "az"), we should 26 to it.

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> groupStrings(vector<string>& strings) {  
4:      unordered_map<string, vector<string>> mp;  
5:      for (string s : strings) {  
6:        mp[pattern(s)].push_back(s);  
7:      }  
8:      vector<vector<string>> res;  
9:      for (auto it : mp) {  
10:        vector<string> r = it.second;  
11:        sort(r.begin(), r.end());  
12:        res.push_back(r);  
13:      }  
14:      return res;  
15:    }  
16:    string pattern(string &s) {  
17:      string p = "";  
18:      for (int i = 1; i < s.size(); i++) {  
19:        int diff = s[i]-s[i-1];  
20:        if (diff < 0) diff += 26;  
21:        p += "a" + to_string(diff);  
22:      }  
23:      return p;  
24:    }  
25:  };  

158. Read N Characters Given Read4 II - Call multiple times

I was thinking every time you call read, it will read the file from beginning, but it seems not. The following solution fails case ["ab", read(1), read(2)], output should be ["a", "b"]. From the output, I realized that when calling read(), it should maintain the file offset.

1:  class Solution {  
2:  public:  
3:    /**  
4:     * @param buf Destination buffer  
5:     * @param n  Maximum number of characters to read  
6:     * @return  The number of characters read  
7:     */  
8:    int read(char *buf, int n) {  
9:      int i = 0;  
10:      int m = 0;  
11:      int rc = 0;  
12:      while (i < n && (m = read4(buf)) > 0) {  
13:        buf += m;  
14:        i += m;  
15:      }  
16:      return i >= n ? n : i;  
17:    }  
18:  };  

So we need to have a 4 bytes buffer and its pointer as the file offset.

1:  // Forward declaration of the read4 API.  
2:  int read4(char *buf);  
3:  class Solution {  
4:  private:  
5:    char buffer[4];  
6:    int ib = 0;  
7:    int nb = 0;  
8:  public:  
9:    /**  
10:     * @param buf Destination buffer  
11:     * @param n  Maximum number of characters to read  
12:     * @return  The number of characters read  
13:     */  
14:    int read(char *buf, int n) {  
15:      int i = 0;  
16:      while ((i < n) && (ib < nb || (ib = 0) < (nb = read4(buffer)))) {  
17:        buf[i++] = buffer[ib++];  
18:      }  
19:      return i;  
20:    }  
21:  };