String Part2 (time 2)

3 - Pointers (i : begin of interest, j : end of interest, storeIndex, in place save position)

151 Reverse Words in a String

reverse the whole string and then reverse each word. Specifically, use 3 pointers. One

denote the beginning of a new char, another denote the end of a new char, a third pointer

to keep track of the sotre position in the current char (since there maybe multiple space between words, storeIndex <= j)

443 String Compression

Similar to 151 Reverse Words in a String, i will keep track of start position of current repeating char, j will be the end of the repeating char group, storeIndex will keep track where to save the current unique char and its occurrence.

DP

5	Longest Palindromic Substring

Base case1: all 1-length string is palindrome

Base case2: check all s[i][i+1] length 2 string by comparison s[i] with s[i+1]

DP function 2, transition formula for substring length >= 3

if (s[i] == s[j] && table[i + 1][j - 1])

table[i][j] = true

91	Decode Ways

https://www.tianmaying.com/tutorial/LC91

Note: how to handle char '0'

583	Delete Operation for Two Strings

Using brutal recursion to calculate the Longest Common Subsequence will Time Limit Exceeded, just use an array (M * N) to save the temporary result will cut the time complexity from O(2^max(M,N)) to O(M*N), but the space will increase from O(max(M, N)) to O(M*N)

Calculate LCS use DP:
Base case1:
0 == m or 0 == n , LCS = 0
Transition Formula:
if str1[i -1] == str2[j -1]
DP[i][j] = DP[i-1][j-1] + 1;
else
DP[i][j] = max(DP[i][j-1], DP[i - 1][j]);

STL

556	Next Greater Element III

First convert the number to string and then use STL next_permutation function to get the next permutation (i.e the next greater number) and then covert ti back to long number if greater than INT_MAX or less or equal to the original number return -1. Otherwise return the converted value. BUT can you implement the next_permutation function yourself?

Yes, it is simple:

Find num[i] which is the first increasing point compare to num[i - 1]

Also find the nums[j] is the first element from back which >= num[i - 1]

swap num[i - 1] and num[j]

reverse(nums.begin() + i, nums.end())

Validate:

468	Validate IP Address

(a) Check whether the first 4 chars of the string contains '.', if so treat it as a candidate of IPv4, otherwise check if the first 5 chars of the string contains ':' , if so treat it as a candidate of IPv6, otherwise it is "Neither"

(b) For each candidate IPv4 address, split it into 4 parts and check whether each block only contains only digits has length from 1-3, and each block value is within the range of 0-255. If all 4 parts satisfy the constraint then it is a valid IPv4 address.

(c) For each candidate IPv6 address, split it into 8 parts and check whether each parts has length 1-4 and only contains chars from "0123456789abcdefABCDEF", if so it is valid IPv6 address, otherwise it is "Neither".

678	Valid Parenthesis String

Since * can be used as 3 kinds of char, if we do backtrack the complexity can blow up if the string is *****… We need to find a non-trivial method. Without *, we can just use a number to indicate the unmatch. '(' will increment it and ')' will decrement it. We don’t want this number less than 0 all the time and it should be 0 when all the string has been matched. When * is introduced, the number becomes a range, indicating the number of possible unmatched ( found. One * just expand the range by 1. And we can use the same principle to check if the criteria above is within the range.

680	Valid Palindrome II

O(N) time and O(1) space recursive solution:

Intuition

If the beginning and end characters of a string are the same (ie. s[0] == s[s.length - 1]), then whether the inner characters are a palindrome (s[1], s[2], ..., s[s.length - 2]) uniquely determines whether the entire string is a palindrome.

Algorithm

Suppose we want to know whether s[i], s[i+1], ..., s[j] form a palindrome. If i >= j then we are done. If s[i] == s[j] then we may take i++; j--. Otherwise, the palindrome must be either s[i+1], s[i+2], ..., s[j] or s[i], s[i+1], ..., s[j-1], and we should check both cases.

Count:

434. Number of Segments in a String

(1) using stringstream to count the segments which is naive

(2). use regex_replace in the C++11 head <regex>

return regex_replace(regex_replace(s, regex("\\S+"), "x"), regex(" "), "").size();

Inner regex_replace repace every word (matched by regex("\\S+")) with char 'x'

Then the outer regex_replace replace the space " " with ""

Then we get the size of returned std::string ( i.e: std::basic_string<char>)

which is the number of segments

696. Count Binary Substrings

Intuition

We can convert the string s into an array groups that represents the length of same-character contiguous blocks within the string. For example, if s = "110001111000000", then groups = [2, 3, 4, 6].

For every binary string of the form '0' * k + '1' * k or '1' * k + '0' * k, the middle of this string must occur between two groups.

Let's try to count the number of valid binary strings between groups[i] and groups[i+1]. If we have groups[i] = 2, groups[i+1] = 3, then it represents either "00111" or "11000". We clearly can make min(groups[i], groups[i+1]) valid binary strings within this string. Because the binary digits to the left or right of this string must change at the boundary, our answer can never be larger.

Algorithm

Let's create groups as defined above. The first element of s belongs in it's own group. From then on, each element either doesn't match the previous element, so that it starts a new group of size 1; or it does match, so that the size of the most recent group increases by 1.

Afterwards, we will take the sum of min(groups[i-1], groups[i]).

647	Palindromic Substrings

(a) Brute Force:
The naive solution is O(N^3) which is simply, for loop each start position form (0 to n-1), and check each length of the sub string (from 1 to n) and check whether it is a palindrome string if so increase the counter by 1. Finally return the counter value.

(b) Expand around center (O(N^2))

Intuition

Let N be the length of the string. The middle of the palindrome could be in one of 2N - 1 positions: either at letter or between two letters.

For each center, let's count all the palindromes that have this center. Notice that if [a, b] is a palindromic interval (meaning S[a], S[a+1], ..., S[b] is a palindrome), then [a+1, b-1] is one too.

Algorithm

For each possible palindrome center, let's expand our candidate palindrome on the interval [left, right] as long as we can. The condition for expanding is left >= 0 and right < N and S[left] == S[right]. That means we want to count a new palindrome S[left], S[left+1], ..., S[right].

(c) There is a Manacher's O(N) algorithm (2*N in fact) I need to study some day.

https://leetcode.com/problems/palindromic-substrings/solution/

Define a 2-D dp array of bool, initialize all the n * n elements to false.
In a double for loop, where i is from n - 1 to 0 inclusive. And Inner loop
controller j is from i to n - 1 inclusive, if s[i] == s[j] and (j - i <= 1 || dp[i + 1][j - 1])
set dp[i][j] to true as well. add dp[i][j] to the total number of palindrome count while
traversal.

Longest

3	Longest Substring Without Repeating Characters

Sliding window O(N) time, O(K) space where K is the size of set Define a hash set and loop over each char in the string from left to right while the right side of the window is still within the range of string size check whether the current char is already in the set, if not: insert it into the set and move the right side right by 1, update maxCount if the current window size is greater that maxCount. If yes, erase the current element indicated by the left side of the window from the set and move the left side of window right by one. After the right side of the window exceeds string size. maxCount will be the longest substring without repeating characters.

5	Longest Palindromic Substring

Base case1: all 1-length string is palindrome
Base case2: check all s[i][i+1] length 2 string by comparison s[i] with s[i+1]
DP function 2, transition formula for substring length >= 3
if (s[i] == s[j] && table[i + 1][j - 1])
table[i][j] = true

522 Longest Uncommon Subsequence II

(1) define a string to int map to save the frequency of each string

(2) define a vector of map element pair and sort it in descending order of string size

(3) For each string in the sorted vector, if all the other string coming before it is
NOT a super string of it then we use its size as LUS. If each pair of string have
sub string relation then the longest uncommon subsequence doesn't exist

Hash Map

17 Letter Combinations of a Phone Number

Define a map from digit to its chars, and loop over each digit and the chars add that char to the string array combination result.

// O(len1 * len2 * ... lenN), where lenI is the # of chars digit[i] map to
class Solution {
public:
vector<string> letterCombinations(string digits) {
unordered_map<char, string> mp =
{{'0', ""}, {'1', ""}, {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
vector<string> res;
if (digits.empty())
return res;

res.push_back("");
for (const auto& d : digits) {
vector<string> tmp;
for (const auto& c : mp[d]) {
for (const auto& r : res) {
tmp.push_back(r + c);
}
}
res.swap(tmp);
}

return res;
}
};

String match:

28 Implement strStr()

http://blog.csdn.net/v_july_v/article/details/7041827
KMP algorithm is using the known info from previous comparison to improve the naive string match algorithm.

// KMP O(N + M) time and O(1) space
class Solution {
public:

int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();

int i = 0, j = 0;
while (i < n && j < m) {
if (-1 == j || haystack[i] == needle[j]) { // match
// ① 如果j == -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
i++;
j++;
} else {
// ② 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}

if (j == m)
return i - j;

return -1;
}

void calculateNext(string str,vector<int>& next) {
if (next.empty())
return;

int M = next.size();
next[0] = -1;
int k = -1;
int j = 0;
while (j < M - 1) {
// str[j]: post-fix, str[k] prefix
if (-1 == k || str[k] == str[j]) {
k++;
j++;
next[j] = k;

} else
k = next[k];
}

686	Repeated String Match

The maximum repeated time for A is (B.size()/A.size() + 2), loop 1 time of A until (B.size()/A.size() + 2) times of A to check whether B is a sub string if so, return loop index, otherwise return -1.

a: "abc" "abc" "abc"
b: "c abc a" - in this case we still need 3 copies of a, but a.len / b.len (5/3) only give you 1
That’s why we want to add at least 2 copies.

459. Repeated Substring Pattern (need to learn KMP algorithm deeper )
// Solution 1
str + str means doubling, (str + str).substr(1, str.size() * 2 - 2) means removing the first char of the first half and the last char of the second half.
If there is no pattern, both of the first copy and the second copy will be changed, so str will not be found in (str + str).substr(1, str.size() * 2 - 2).
If there is a pattern, the first char of str can still be found in the first half, and the last char of str can also be found in the second half. Here is an example: abcabc is the original string, and (bcabc abcab) includes abcabc.

Priority Queue:

767	Reorganize String

O(N) time, O(N) space solution, using priority_queue with a helper queue to filter the already 0-counted pairs.
For priority queue, the highest priority element (maximum count element here, therefore we want the pair in the priority queue be pair<int, char> rather than pair<char, int>, the later will sort the queue by descending alphabetical order, the first will sort the array according to the int number in descending order) is always at the front.

Parsing:

385	Mini Parser

Using istringstream to split the input separated by ',' and '[]'. If the current part is a integer

return NestInteger(integer). Otherwise create a list and DFS recursively add the deserialize result and return the list.

722	Remove Comments

(a) we join the vector of string into one string using \n

(b) regex replace the comments using empty string

But why we need the ? in the regex which matches comments?

"//.*|/\\*(.|\n)*?\\*/"

Others:

541	Reverse String II

If string size less or equal than k, reverse the whole string and return it
Otherwise, for loop every kth char in the string, if i is odd multiple times of k
reverse the k chars until i and keep record of the previous postion of i (say pre).
When exit if the # of chars between pre till the end is less than or equal to k,
reverse all of them and return the modified string.

38	Count and Say

To generate the nth term, just count and say the n-1th term.
The following are the terms from n=1 to n=10 of the count-and-say sequence:

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
10.     13211311123113112211

class Solution {
public:
string countAndSay(int n) {
if (0 == n)
return "";

string res = "1";
while (--n) {
string cur = "";
for (int i = 0; i < res.size(); i++) {
int count = 1;
while (i + 1 < res.size() && res[i] == res[i + 1]) {
count++;
i++;
}

cur += to_string(count) + res[i];
}
res = cur;
}

return res;
}
};

6	ZigZag Conversion

The main difficulty here is how to swap increase to decrease row index. The indices are like

this : 0, 1,2, 0, 1, 2, 0, 1, 2. So we could swap increase to decrease when the row number reach numRows - 1, and swap it back to increase when row number is 0.

Be careful about corner cases like string size less or equal than total row numbers or only have 1 row.

string convert(string s, int numRows) {

if (s.size() <= numRows || 1 == numRows)

return s;

vector<string> rows(numRows);

int row = 0;

int step = 1;

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

rows[row].push_back(s[i]);

if (0 == row)

step = 1;

else if (numRows - 1 == row)

step = -1;

row += step;

}

string res;

for (const auto& r : rows)

res += r;

return res;

}

609	Find Duplicate File in System

Idea is simple: Use a hashmap with names vectors to store all files contents, and then prints the duplicates

the time complexity is O(n^2 * k) since in worse case we might need to compare every file to all others. k is the file size, n is the number of input files.

However, In a real life solution we will not hash the entire file content, since it’s not practical ( a file system would have GB even TB size). Instead we will first map all the files according to size. Files with different sizes are guaranteed to be different. We will than hash a small part of the files with equal sizes (using MD5 for example). Only if the md5 is the same, we will compare the files byte by byte

22	Generate Parentheses

The idea is intuitive. Use two integers to count the remaining left parenthesis (n) and the right parenthesis (m) to be added. At each function call add a left parenthesis if n >0 and add a right parenthesis if m>0. Append the result and terminate recursive calls when both m and n are zero.

71	Simplify Path

Define a vector of string to mimic stack. Use getline of stringstream to split the path string. skip "." and "", when meet ".." if the stack is not empty() pop_back, otherwise if the string is not ".." push_back. Finally, for loop the vector<string> to construct the simplified path.

93	Restore IP Addresses

Loop the 4 parts of IP for size 1,2,3 and for these four parts length sums to the original string size.Convert them to integer and if all the four parts are less than 255. Append all 4 parts together separated by the '.', if the IP size is equal to the original string size plus 3, put it in the result array.

165	Compare Version Numbers

For loop each group of the version number part separated by the '.' and compare them if version1 > version 2 return 1, else if version 1 < version 2 return -1, otherwise continue comparing the next part of the version number. If in the end no early return that means the two version numbers are the same.

227	Basic Calculator II

Use two stacks : one to save operators, one to save oprands. Every time, if we get a digit, then update curNum, if we get an operator, then it means we get a complete oprand, which is saved in curNum; if the last operator is * or /, then calculate it, otherwise, just save curNum and s[i] (new operator) in the stacks. At last, the opS stack has only “+” & “-”, which are the sign of the corresponding operands saved in numS. Then we do sum to get the result.

For this kind of small interview question, you can mention but won't have time to implement the complete solution from the text book (Yanwei min, Data structure and algorithm), it is usually a simplified version.

Search This Blog

leetcode solution