Complete the implementation of an autocorrect function. Given
a search query string, the function should return all words which are anagrams.
Given 2 arrays, words[n], and queries[q], for each
query, return an array of the strings that are anagrams, sorted alphabetically ascending.
Note: An anagram is any string that can be formed by rearranging the letters of a string.
Function Description
Complete the function getSearchResults in the editor.
Constraints
- 1 ≤ n, q ≤ 5000
- 1 ≤ length of words[i], length of queries[i] ≤ 100
- It is guaranteed that each query word has at least one anagram in the word list
Example 1
Input:
n = 2
words = ["duel", "speed", "dule", "cars"]
queries = ["dpede", "deul"]Output:
[["speed"], ["duel", "dule"]]Explanation: The only anagram of "speed" is "spede". Both "duel" and "dule" are anagrams of "deul". Return [["speed"], ["duel", "dule"]].
解法
字符排序签名分组，每个 query 取签名查表并排序。O((n + q) · L log L)。
def getSearchResults(words, queries):
groups = {}
for w in words:
key = "".join(sorted(w))
groups.setdefault(key, []).append(w)
for v in groups.values(): v.sort()
return [groups.get("".join(sorted(q)), []) for q in queries]class Solution {
String[][] getSearchResults(String[] words, String[] queries) {
java.util.HashMap<String, java.util.List<String>> g = new java.util.HashMap<>();
for (String w : words) {
char[] ca = w.toCharArray(); java.util.Arrays.sort(ca);
g.computeIfAbsent(new String(ca), k -> new java.util.ArrayList<>()).add(w);
}
for (var v : g.values()) java.util.Collections.sort(v);
String[][] res = new String[queries.length][];
for (int i = 0; i < queries.length; i++) {
char[] ca = queries[i].toCharArray(); java.util.Arrays.sort(ca);
var v = g.get(new String(ca));
res[i] = v == null ? new String[0] : v.toArray(new String[0]);
}
return res;
}
}class Solution {
public:
vector<vector<string>> getSearchResults(vector<string>& words, vector<string>& queries) {
unordered_map<string, vector<string>> g;
for (auto& w : words) { string k = w; sort(k.begin(), k.end()); g[k].push_back(w); }
for (auto& [k, v] : g) sort(v.begin(), v.end());
vector<vector<string>> res;
for (auto& q : queries) {
string k = q; sort(k.begin(), k.end());
auto it = g.find(k);
res.push_back(it == g.end() ? vector<string>() : it->second);
}
return res;
}
};Consider a string, S, that is a series of characters, each followed by its frequency as an integer.
The string is not compressed correctly, so there may be multiple occurrences of the same character.
A properly compressed string will consist of one instance of each character in alphabetical order followed by the
total count of that character within the string.
Function Description
Complete the function betterCompression in the editor.
betterCompression has the following parameter:
S: a compressed string
Return
string: the properly compressed string
Constraints
1 'a' 1 ≤ frequency of each character in S ≤ 1000
Example 1
Input:
S = "a3c9b2c1"Output:
"a3b2c10"Explanation: The string 'a3c9b2c1' has two instances where 'c' is followed by a count: once with 9 occurrences, and again with 1. It should be compressed to 'a3b2c10'.
Example 2
Input:
S = "a12b56c1"Output:
"a12b56c1"Explanation: Noting is changed because character occurred only once and they are already sorted ascending.
解法
解析 S：交替读取 (字母, 数字串)。累加每个字母的总次数到 hashmap，按字母升序输出 字母 + 总次数。O(|S|)。
def betterCompression(S):
cnt = {}
i = 0
while i < len(S):
ch = S[i]; i += 1
j = i
while j < len(S) and S[j].isdigit(): j += 1
cnt[ch] = cnt.get(ch, 0) + int(S[i:j])
i = j
return "".join(c + str(cnt[c]) for c in sorted(cnt))class Solution {
String betterCompression(String S) {
java.util.TreeMap<Character, Integer> cnt = new java.util.TreeMap<>();
int i = 0;
while (i < S.length()) {
char ch = S.charAt(i++);
int j = i;
while (j < S.length() && Character.isDigit(S.charAt(j))) j++;
cnt.merge(ch, Integer.parseInt(S.substring(i, j)), Integer::sum);
i = j;
}
StringBuilder sb = new StringBuilder();
for (var e : cnt.entrySet()) sb.append(e.getKey()).append(e.getValue());
return sb.toString();
}
}class Solution {
public:
string betterCompression(string S) {
map<char, int> cnt;
int i = 0;
while (i < (int)S.size()) {
char ch = S[i++];
int j = i;
while (j < (int)S.size() && isdigit(S[j])) j++;
cnt[ch] += stoi(S.substr(i, j - i));
i = j;
}
string res;
for (auto& [k, v] : cnt) res += k + to_string(v);
return res;
}
};Two strings are said to be the same if they are of the same length and have the same character at each index.
Backspacing in a string removes the previous character in the string.
Given two strings containing lowercase English letters and the character # which represents a backspace key,
determine if the two final strings are equal. Return 1 if they are equal or 0 if they are not.
Note that backspacing an empty string results in an empty string.
Function Description
Complete the function compareStrings in the editor below.
compareStrings has the following parameter(s):
string s1: the first stringstring s2: the second string Returnsint: either0or1
Constraints
1 5Both s1 and s2 contain lowercase English letters and/or the char '#' only :)
Example 1
Input:
s1 = "axx#b#b#c"
s2 = "axbdf#c#c"Output:
1Explanation:
In the first string, one 'x' and one 'b' are backspaced over. The first string becomes axbc.
The second string also becomes axbc. The answer is 1.
解法
分别用栈处理两个串：遇 '#' 弹栈。比较最终栈。O(n)。
def compareStrings(s1, s2):
def proc(s):
st = []
for c in s:
if c == '#':
if st: st.pop()
else:
st.append(c)
return "".join(st)
return 1 if proc(s1) == proc(s2) else 0class Solution {
int compareStrings(String s1, String s2) {
return proc(s1).equals(proc(s2)) ? 1 : 0;
}
String proc(String s) {
StringBuilder st = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '#') { if (st.length() > 0) st.setLength(st.length() - 1); }
else st.append(c);
}
return st.toString();
}
}class Solution {
public:
string proc(string s) {
string st;
for (char c : s) {
if (c == '#') { if (!st.empty()) st.pop_back(); }
else st += c;
}
return st;
}
int compareStrings(string s1, string s2) {
return proc(s1) == proc(s2) ? 1 : 0;
}
};