LeetCode Longest Common Prefix

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

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"


Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.


Note:

All given inputs are in lowercase letters a-z.

class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{
if (strs.size() == 0)
return "";
int max_common = INT_MAX;
string longest_common = "";
for (int i = 0; i < strs.size(); i++)
if (strs[i].size() < max_common)
max_common = strs[i].size();
for (int i = 0; i < max_common; i++) {
for (int j = 1; j < strs.size(); j++) {
if (strs[j][i] != strs[0][i])
return longest_common;
}
longest_common += strs[0][i];
}
return longest_common;
}
};

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size(), i = 0;
if (n == 0)return "";
while (true) {
bool valid = true;
for (int j = 0; j < n; ++j) {
if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {
valid = false;
break;
}
}
if (!valid)break;
else ++i;
}
return strs[0].substr(0, i);
}
};

LeetCode Roman to Integer

Roman numerals are represented by seven different symbols: IVXLCD and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

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

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.


Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

class Solution {
public:
int romanToInt(string s)
{
vector<int> nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
vector<string> symbol = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
int ans = 0;
for (int i = nums.size() – 1; i >= 0; i–) {
int sz = symbol[i].size();
while (s.size() >= sz && s.substr(0, sz) == symbol[i]) {
ans += nums[i];
s = s.substr(sz);
}
}
return ans;
}
};

LeetCode Integer to Roman

Roman numerals are represented by seven different symbols: IVXLCD and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

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

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.


Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

class Solution {
public:
string work(int num, string cur)
{
if (num >= 1000)
return work(num – 1000, cur + "M");
if (num >= 500) {
if (num >= 900)
return work(num – 900, cur + "CM");
return work(num – 500, cur + "D");
}
if (num >= 100) {
if (num >= 400)
return work(num – 400, cur + "CD");
return work(num – 100, cur + "C");
}
if (num >= 50) {
if (num >= 90)
return work(num – 90, cur + "XC");
return work(num – 50, cur + "L");
}
if (num >= 10) {
if (num >= 40)
return work(num – 40, cur + "XL");
return work(num – 10, cur + "X");
}
if (num >= 5) {
if (num >= 9)
return work(num – 9, cur + "IX");
return work(num – 5, cur + "V");
}
if (num < 5) {
if (num >= 4)
return work(num – 4, cur + "IV");
while (num > 0) {
cur += "I";
num–;
}
return cur;
}
}
string intToRoman(int num) { return work(num, ""); }
};

class Solution {
public:
string intToRoman(int num)
{
vector<int> nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
vector<string> symbol = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
string ans = "";
for (int i = nums.size() – 1; i >= 0; i--) {
while (num >= nums[i]) {
ans += symbol[i];
num -= nums[i];
}
}
return ans;
}
};

LeetCode Container With Most Water

Given n non-negative integers a1a2, …, a, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

class Solution {
public:
int maxArea(vector<int>& height)
{
int mA = 0, i = 0, j = height.size() – 1;
while (i != j) {
int cur = min(height[i], height[j]) * (j – i);
if (cur > mA)
mA = cur;
if (height[i] < height[j])
i++;
else
j--;
}
return mA;
}
};

LeetCode Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26


Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).


Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

DP转移公式如下：
$$\begin{cases}dp[i] += dp[i-1] & \text{if s[i] \in [1,9]}\\dp[i] += dp[i-2] & \text{if s[i-1]s[i] \in [10,26]}\\\end{cases}$$

class Solution {
public:
int numDecodings(string s)
{
if (s == "" || s[0] == ‘0’)
return 0;
s = "^" + s;
int n = s.size();
vector<int> dp(n, 0);
dp[0] = dp[1] = 1;
for (int i = 2; i < n; i++) {
if (s[i] >= ‘1’ && s[i] <= ‘9’)
dp[i] += dp[i – 1];
if ((s[i – 1] == ‘1’ && s[i] >= ‘0’ && s[i] <= ‘9’) || (s[i – 1] == ‘2’ && s[i] >= ‘0’ && s[i] <= ‘6’))
dp[i] += dp[i – 2];
}
return dp[n – 1];
}
};

LeetCode Distinct Subsequences

115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

It’s guaranteed the answer fits on a 32-bit signed integer.

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^


Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
^  ^^
babgbag
^^^

DP转移公式如下：
$$dp[i][j]=\begin{cases}dp[i-1][j] & \text{if S[i]\neq T[j]}\\dp[i-1][j]+dp[i-1][j-1] & \text{if S[i]=T[j]}\\\end{cases}$$

class Solution {
public:
int numDistinct(string s, string t)
{
if (s == "")
return 0;
if (t == "")
return 1;
s = "^" + s;
t = "^" + t;
int n = s.size(), m = t.size();
vector<vector<int> > dp(n, vector<int>(m, 0));
for (int i = 0; i < n; i++)
dp[i][0] = 1; // ‘*’ -> ” 1 sub
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = dp[i – 1][j];
if (s[i] == t[j])
dp[i][j] += dp[i – 1][j – 1];
}
}
return dp[n – 1][m – 1];
}
};

class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
if(n > m) return 0;
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
for(int i = 0; i < m; ++i) dp[i][0] = 1;
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
};

LeetCode Palindrome Partitioning II

132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

class Solution {
public:
int minCut(string s)
{
int n = s.size();
vector<vector<bool> > dp(n, vector<bool>(n, false));
for (int i = 0; i < n; i++)
dp[i][i] = true;
vector<int> cut(n, 0); // # of cut for s[0,j]
for (int j = 0; j < n; j++) {
cut[j] = j; // set maximum # of cut
for (int i = 0; i <= j; i++) {
if (s[i] == s[j] && (j – i <= 1 || dp[i + 1][j – 1])) {
dp[i][j] = true;
if (i > 0) // if need to cut, add 1 to the previous cut[i-1]
cut[j] = min(cut[j], cut[i – 1] + 1);
else // if [0…j] is palindrome, no need to cut cut[j] = 0;
}
}
}
return cut[n – 1];
}
};

.......aba...
|<-X->| ^
|<---Y-->|


class Solution {
public:
int minCut(string s)
{
int n = s.size();
vector<int> cuts(n + 1, 0); // cuts[i] 表示前i个字符切成回文子串，最少的刀数
for (int i = 0; i <= n; ++i)
cuts[i] = i – 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; i – j >= 0 && i + j < n && s[i – j] == s[i + j]; ++j) // 最后一个是奇数长回文子串
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j] + 1);
for (int j = 1; i – j + 1 >= 0 && i + j < n && s[i – j + 1] == s[i + j]; ++j) // 最后一个是偶数长回文子串
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j + 1] + 1);
}
return cuts[n];
}
};

class Solution {
public:
void preprocess(const string &s, vector<vector<int>> &dp) {
int n = s.size();
for (int i = 0; i < n; ++i)dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j < n && s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
dp[i][j] = 1;
}
}
}
}
int minCut(string s) {
int n = s.size();
if (n == 0 || n == 1)return 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
preprocess(s, dp);
vector<int> dp2(n, 0);
for (int j = 1; j < n; ++j) {
dp2[j] = dp2[j - 1] + 1;
for (int i = j - 1; i >= 0; --i) {
if (dp[i][j] == 1) {
int pre_cut = i > 0 ? dp2[i - 1] + 1 : 0;
dp2[j] = min(dp2[j], pre_cut);
}
}
}
return dp2[n - 1];
}
};

LeetCode Palindrome Number

9. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true


Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.


Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.


Coud you solve it without converting the integer to a string?

class Solution {
public:
bool isPalindrome(int x)
{
if (x < 10)
return x >= 0;
if (x % 10 == 0)
return false;
int y = 0;
while (x > y) {
y = y * 10 + x % 10;
if (x == y) //76567
return true;
x /= 10;
if (x == y) //765567
return true;
}
return false;
}
};

class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
if(x == 0) return true;
if(x % 10 == 0) return false;

vector<int> digits;
while(x != 0) {
digits.push_back(x % 10);
x /= 10;
}
int l = 0, r = digits.size() - 1;
while(l < r) {
if(digits[l] != digits[r]) return false;
++l;
--r;
}
return true;
}
};

LeetCode String to Integer (atoi)

8. String to Integer (atoi)

Implement atoi which converts a string to an integer.

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.

Note:

• Only the space character ' ' is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: "42"
Output: 42


Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.


Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.


Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.

If the converted value would be out of the range of representable values by an int, it causes undefined behavior. Seestrtol for a more robust cross-platform alternative when this is a possibility.

class Solution {
public:
int myAtoi(string str)
{
int i = 0;
while (i < str.size() && str[i] == ‘ ‘)
i++;
string tmp = str.substr(i);
if (tmp.size() == 0 || (tmp.size() == 1 && (tmp[0] < ‘0’ || tmp[0] > ‘9’)))
return 0;
string digits = (tmp[0] == ‘-‘ || tmp[0] == ‘+’) ? tmp.substr(1) : tmp;
double ans = 0;
for (int i = 0; i < digits.size(); i++)
if (digits[i] < ‘0’ || digits[i] > ‘9’)
break;
else
ans = ans * 10 + (digits[i] – ‘0’);
ans = (tmp[0] == ‘-‘) ? -ans : ans;
if (ans > INT_MAX)
return INT_MAX;
else if (ans < INT_MIN)
return INT_MIN;
else
return ans;
}
};

class Solution {
public:
bool isDigit(char c) {
return c >= '0'&&c <= '9';
}
int myAtoi(string str) {
int ans = 0;
bool neg = false;
int i = 0, n = str.size();
while (str[i] == ' '&&i < n)++i;
if (i < n) {
if (str[i] == '-') {
neg = true;
++i;
} else if (str[i] == '+')++i;
while (i < n&&isDigit(str[i])) {
int digit = str[i] - '0';
if (!neg && (ans > INT_MAX / 10 || (ans == INT_MAX / 10 && digit >= 7)))return INT_MAX;
if (neg && (-ans < INT_MIN / 10 || (-ans == INT_MIN / 10 && digit >= 8)))return INT_MIN;
ans = ans * 10 + digit;
++i;
}
}
if (neg)ans = -ans;
return ans;
}
};

LeetCode Reverse Integer

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321


Example 2:

Input: -123
Output: -321


Example 3:

Input: 120
Output: 21


Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

class Solution {
public:
int reverse(int x)
{
unsigned int y = (x > 0) ? x : -x;
double ans = 0;
while (y) {
ans = ans * 10 + (y % 10);
y = y / 10;
}
if (ans > INT_MAX)
return 0;
return x < 0 ? -ans : ans;
}
};

class Solution {
public:
int reverse(int x) {

int y = 0;
while (x != 0) {
int reminder = x % 10;
x /= 10;
if (y > INT_MAX / 10 || (y == INT_MAX / 10 && reminder > 7))return 0;
if (y < INT_MIN / 10 || (y == INT_MIN / 10 && reminder < -8))return 0;
y = y * 10 + reminder;

}
return y;
}
};