1408. String Matching in an Array

Given an array of string words. Return all strings in words which is substring of another word in any order. 

String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 30
• words[i] contains only lowercase English letters.
• It’s guaranteed that words[i] will be unique.

给定一个字符串数组，如果某个字符串是其他字符串的子串，则输出，找出所有这种字符串。

简单题，直接两遍for循环查找即可，代码如下：

class Solution {
public:
	vector<string> stringMatching(vector<string>& words) {
		vector<string> ans;
		for (int i = 0; i < words.size(); ++i) {
			for (int j = 0; j < words.size(); ++j) {
				if (i == j)continue;
				if (words[j].find(words[i]) != string::npos) {
					ans.push_back(words[i]);
					break;
				}
			}
		}
		return ans;
	}
};

本代码提交AC，用时8MS。

1410. HTML Entity Parser

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

• Quotation Mark: the entity is " and symbol character is ".
• Single Quote Mark: the entity is ' and symbol character is '.
• Ampersand: the entity is & and symbol character is &.
• Greater Than Sign: the entity is > and symbol character is >.
• Less Than Sign: the entity is < and symbol character is <.
• Slash: the entity is ⁄ and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Example 1:

Input: text = "& is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the & entity by &

Example 2:

Input: text = "and I quote: "...""
Output: "and I quote: \"...\""

Example 3:

Input: text = "Stay home! Practice on Leetcode :)"
Output: "Stay home! Practice on Leetcode :)"

Example 4:

Input: text = "x > y && x < y is always false"
Output: "x > y && x < y is always false"

Example 5:

Input: text = "leetcode.com⁄problemset⁄all"
Output: "leetcode.com/problemset/all"

Constraints:

• 1 <= text.length <= 10^5
• The string may contain any possible characters out of all the 256 ASCII characters.

给定一个HTML字符串，要求把其中的特殊符号转换为其原来的表示。

简单题，遍历字符串，找到以&开头，以;结尾的子串，根据情况把它转换为原来的字符即可。请注意，有可能该子串不属于文中6种情况中的任何一种，此时不需要转义，直接原样拷贝。代码如下：

class Solution {
public:
	string entityParser(string text) {
		int n = text.size(), i = 0;
		string ans = "";
		while (i < n) {
			while (i < n&&text[i] != '&') {
				ans.push_back(text[i]);
				++i;
			}
			if (i >= n)break;
			int j = i + 1;
			while (j < n&&text[j] != ';')++j;
			string mark = text.substr(i, j - i + 1);
			if (mark == "&quot;")ans.push_back('\"');
			else if (mark == "&apos;")ans.push_back('\'');
			else if (mark == "&amp;")ans.push_back('&');
			else if (mark == "&gt;")ans.push_back('>');
			else if (mark == "&lt;")ans.push_back('<');
			else if (mark == "&frasl;")ans.push_back('/');
			else ans += mark;
			i = j + 1;
		}
		return ans;
	}
};

本代码提交AC，用时460MS。

844. Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

给定两个字符串，其中包含小写字母和#，#表示删除前一个字符。问这两个字符串的最终结果是否一致。

这道题如果不考虑Follow up的话很简单，新建一个string，看到字母就push_back，看到#就pop_back，最后看剩余字符串是否相等即可。

但是Follow up要求只使用O(1)的空间，这就需要思考一下了。思路是这样的，从后往前处理两个字符串，统计#的数目，模拟删除过程，直到无法删除找到一个能被留在最终字符串中的字母，比较S和T的这个字符是否相等。完整代码如下：

class Solution {
public:
	bool backspaceCompare(string S, string T) {
		int i = S.size() - 1, j = T.size() - 1;
		while (i >= 0 || j >= 0) {
			int skipS = 0, skipT = 0;
			while (i >= 0) {
				if (S[i] == '#') {
					++skipS;
					--i;
				}
				else if (skipS > 0) {
					--skipS;
					--i;
				}
				else {
					break;
				}
			}

			while (j >= 0) {
				if (T[j] == '#') {
					++skipT;
					--j;
				}
				else if (skipT > 0) {
					--skipT;
					--j;
				}
				else {
					break;
				}
			}

			if ((i >= 0) != (j >= 0))return false;
			if (i >= 0 && S[i] != T[j])return false;
			--i;
			--j;
		}
		return true;
	}
};

本代码提交AC，用时0MS。

1374. Generate a String With Characters That Have Odd Counts

Given an integer n, return a string with n characters such that each character in such string occurs an odd number of times.

The returned string must contain only lowercase English letters. If there are multiples valid strings, return any of them.  

Example 1:

Input: n = 4
Output: "pppz"
Explanation: "pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".

Example 2:

Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".

Example 3:

Input: n = 7
Output: "holasss"

Constraints:

• 1 <= n <= 500

简单题。要求构造一个长度为n的字符串，使得字符串中所有字符出现的频率都为奇数。不要被样例迷惑了。如果n为奇数，直接重复一个字符n次即可；如果n为偶数，则重复一个字符n-1次，外加另一个字符。

完整代码如下：

class Solution {
public:
	string generateTheString(int n) {
		if (n % 2 == 0) {
			return string(n - 1, 'a') + "b";
		}
		else {
			return string(n, 'a');
		}
	}
};

本代码提交AC，用时0MS。

1366. Rank Teams by Votes

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position. 

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

Constraints:

• 1 <= votes.length <= 1000
• 1 <= votes[i].length <= 26
• votes[i].length == votes[j].length for 0 <= i, j < votes.length.
• votes[i][j] is an English upper-case letter.
• All characters of votes[i] are unique.
• All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

给定很多人对很多team的打分排序列表，如果一个队排在前面的名次越多，则其最终名次越高，据此输出最终排序列表。

规则很复杂，其实很简单。设计一个Team的类，它有一个scores数组，scores[i]表示这个队被多少人投票排在了第i名。由于最多只有26个队，所以scores的维度为26。对Team自定义排序函数，排序规则是依次比较scores的每个元素大小，如果都相等的话，最后比较name的大小。

完整代码如下：

const int MAXN = 26;
class Team {
public:
	char name;
	vector<int> scores;

	Team() :name(0) {
		scores.resize(MAXN, 0);
	};

	bool operator<(const Team& t) {
		for (int i = 0; i < MAXN; ++i) {
			if (scores[i] > t.scores[i]) {
				return true;
			}
			else if (scores[i] < t.scores[i]) {
				return false;
			}
		}
		return name < t.name;
	}
};

class Solution {
public:
	string rankTeams(vector<string>& votes) {
		vector<Team> teams(MAXN, Team());
		for (int j = 0; j < votes[0].size(); ++j) {
			int idx = votes[0][j] - 'A';
			teams[idx].name = votes[0][j]; // 出现的team name
		}
		for (int i = 0; i < votes.size();++i) {
			for (int j = 0; j < votes[i].size(); ++j) {
				int idx = votes[i][j] - 'A';
				++teams[idx].scores[j];
			}
		}
		vector<Team> showups;
		for (int i = 0; i < MAXN; ++i) {
			if (teams[i].name != 0) {
				showups.push_back(teams[i]);
			}
		}
		sort(showups.begin(), showups.end());
		string ans = "";
		for (int i = 0; i < showups.size(); ++i) {
			ans += showups[i].name;
		}
		return ans;
	}
};

本代码提交AC，用时20MS。

LeetCode Judge Route Circle Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place. The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle. Example 1:

Input: "UD"
Output: true

Input: "LL"
Output: false

LeetCode Exclusive Time of Functions Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions. Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function. A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0. Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id. Example 1:

Input:
n = 2
logs =
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

1. Input logs will be sorted by timestamp, NOT log id.
2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
3. Two functions won’t start or end at the same time.
4. Functions could be called recursively, and will always end.
5. 1 <= n <= 100