String Series
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.
class Solution {
public:
int lengthOfLastWord(string s) {
int len = 0;
if (s.empty()) return 0;
const int n = s.size();
for (int i=0; i<n; i++) {
if (s[i] != ' ') len++;
else {
while (i<n && s[i]==' ') i++;
if (i<n && s[i]!=' ') len = 1;
}
}
return len;
}
};
Write a function to find the longest common prefix string amongst an array of strings.
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
if (strs.empty()) return res;
for (int i=0; i<strs[0].size(); i++) {
char temp = strs[0][i];
for (int j=1; j<strs.size(); j++) {
if (i>=strs[j].size() || strs[j][i]!=temp)
return res;
}
res+=temp;
}
return res;
}
};
class Solution {
public:
void reverseWords(string &s) {
istringstream input(s);
string res, temp;
while(input>>temp)
res = " "+ temp + res;
s = res.empty()?res: res.substr(1);
}
};
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
class Solution {
public:
string largestNumber(vector<int>& nums) {
const int n = nums.size();
vector<string> str(n);
for (int i=0; i<n; i++)
str[i] = to_string(nums[i]);
sort(str.begin(), str.end(), [](string &i, string &j){return i+j>j+i;});
string res;
for (string s:str) res+=s;
return res[0]=='0'?"0":res;
}
};
Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size()-1;
while (left < right) {
int mid = left+(right-left)/2;
if (nums[left] < nums[right])
return nums[left];
else if (nums[left]<nums[mid])
left = mid;
else if (nums[left]>nums[mid])
right = mid;
else
left++;
}
return nums[left];
}
};
Follow up for “Find Minimum in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why?
In the same way, it can be used in the duplicated cases.
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size()-1;
while (left < right) {
int mid = left+(right-left)/2;
if (nums[left] < nums[right])
return nums[left];
else if (nums[left]<nums[mid])
left = mid;
else if (nums[left]>nums[mid])
right = mid;
else
left++;
}
return nums[left];
}
};
String
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.
class Solution {
public:
int myAtoi(string str) {
if (str.empty()) return 0;
long long res = 0;
bool neg = false;
int i = 0;
while (str[i]==' ') i++;
if (str[i]=='+') {neg = false;i++;}
else if(str[i]=='-') {neg = true;i++;}
for (; i<str.size(); i++) {
if (str[i]<'0' || str[i]>'9') break;
res = res*10 + (str[i]-'0');
if (neg && -res<INT_MIN) return INT_MIN;
if (!neg && res>INT_MAX) return INT_MAX;
}
if (neg)
return -res<INT_MIN?INT_MIN:-res;
else
return res>INT_MAX?INT_MAX:res;
}
};
Palindromic Series
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: “babad”
Output: “bab”
Input: “cbbd”
Output: “bb”
class Solution {
public:
string longestPalindrome(string s) {
const int n = s.size();
if (n<2) return s;
int i = 1;
int res = 0, begin = 0;
for (int i=0; i<n; i++) {
int j = i;
while (j<n && s[j]==s[j+1]) j++;
int left = i, right = j;
while (left>=0 && right<n && s[left] == s[right]) {
left--;
right++;
}
if (right-left-1 > res) {
res = right - left -1;
begin = left+1;
}
}
return s.substr(begin, res);
}
};
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.
class Solution {
public:
bool isPalindrome(string s) {
if (s.empty()) return true;
int left=0, right = s.size()-1;
while (left<right) {
while (left<right && !isalnum(s[left])) left++;
while (left<right && !isalnum(s[right])) right--;
if (left>=right) break;
if (tolower(s[left]) != tolower(s[right])) return false;
else {
left++;
right--;
}
}
return true;
}
};
Parentheses Series
Given a string containing just the characters (, ), [, ], { and }, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but ([ and ([)] are not.
class Solution {
public:
bool isValid(string s) {
stack<char> st;
if (s.empty()) return true;
for (int i=0; i<s.size(); i++) {
char sign = s[i];
if (s[i]=='[' || s[i]=='(' || s[i]=='{')
st.push(sign);
else {
if (st.empty()) return false;
if (sign==')') {
if (st.top() != '(') return false;
else st.pop();
}
else if (sign==']') {
if (st.top() != '[') return false;
else st.pop();
}
else {
if (st.top() != '{') return false;
else st.pop();
}
}
}
return st.size()==0;
}
};
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
if (n<=0) return res;
string str;
helper(res, str, 0, n);
return res;
}
void helper(vector<string> &res, string str, int right, int left) {
if (left==0 && right==0) {
res.push_back(str);
return;
}
if (right>0)
helper(res, str+")", right-1, left);
if (left>0)
helper(res, str+"(", right+1, left-1);
}
};
Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring.
For ((), the longest valid parentheses substring is (), which has length = 2.
Another example is )()()), where the longest valid parentheses substring is ()(), which has length = 4.
class Solution {
public:
int longestValidParentheses(string input) {
if (input.empty()) return 0;
stack<int> st;
int last = -1;
int res = 0;
for (int i=0; i<input.size(); i++) {
if (input[i]=='(') st.push(i);
else {
if (st.empty()) last = i;
else {
st.pop();
if (st.empty()) res = max(res, i-last);
else res = max(res, i-st.top());
}
}
}
return res;
}
};
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: “23-45”
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
Output: [-34, -14, -10, -10, 10]
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> res;
if (input.empty()) return res;
const int n = input.size();
for (int i=0; i<n; i++) {
char sign = input[i];
if (sign =='+' || sign=='-' || sign =='*') {
vector<int> temp1 = diffWaysToCompute(input.substr(0, i));
vector<int> temp2 = diffWaysToCompute(input.substr(i+1));
for (int num1:temp1) {
for (int num2:temp2) {
if (sign=='+') res.push_back(num1+num2);
else if (sign=='-') res.push_back(num1-num2);
else res.push_back(num1*num2);
}
}
}
}
if (res.empty())
res.push_back(stoi(input));
return res;
}
};
Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [[7],[2, 2, 3]]
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> curr;
sort(candidates.begin(), candidates.end());
helper(res, curr, candidates, target, 0);
return res;
}
void helper(vector<vector<int>> &res, vector<int>& curr, vector<int>& candidates, int target, int pos) {
if (target==0) {
res.push_back(curr);
return;
}
for (int i=pos; i<candidates.size() && target>0; i++) {
curr.push_back(candidates[i]);
helper(res, curr, candidates, target-candidates[i], i);
curr.pop_back();
}
}
};
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: [[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> curr;
sort(candidates.begin(), candidates.end());
helper(res, curr, candidates, target, 0);
return res;
}
void helper(vector<vector<int>> &res, vector<int>& curr, vector<int>& candidates, int target, int pos) {
if (target==0) {
res.push_back(curr);
return;
}
for (int i=pos; i<candidates.size() && target>0; i++) {
curr.push_back(candidates[i]);
helper(res, curr, candidates, target-candidates[i], i+1);
curr.pop_back();
while (i<candidates.size() && candidates[i]==candidates[i+1]) i++;
}
}
};
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example, If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> curr;
if (n<k) return res;
helper(res, curr, 1, n, k);
return res;
}
void helper(vector<vector<int>> &res, vector<int> &curr, int pos, int n, int k) {
if (k==0) {
res.push_back(curr);
return;
}
for (int i=pos; i<=n && k>0; i++) {
curr.push_back(i);
helper(res, curr, i+1, n, k-1);
curr.pop_back();
}
}
};