Giả sử chúng ta có danh sách các cụm từ, hãy tạo danh sách các câu đố "Trước và Sau". Một cụm từ là chuỗi chỉ chứa chữ cái thường và dấu cách, không có dấu cách ở đầu/cuối và không có dấu cách liên tiếp.
Câu đố "Trước và Sau" được hình thành bằng cách gộp hai cụm từ mà từ cuối của cụm từ đầu trùng với từ đầu của cụm từ sau. Chúng ta phải tìm tất cả các câu đố như vậy từ mọi cặp cụm từ phrases[i] và phrases[j] với i != j. Thứ tự ghép quan trọng, cần xét cả hai chiều. Kết quả là danh sách các chuỗi khác nhau, sắp xếp theo thứ tự từ điển.
Ví dụ, phrases = ["mission statement", "a quick bite to eat", "a chip off the old block", "chocolate bar", "mission impossible", "a man on a mission", "block party", "eat my words", "bar of soap"], đầu ra: ["a chip off the old block party", "a man on a mission impossible", "a man on a mission statement", "a quick bite to eat my words", "chocolate bar of soap"].
Để giải quyết, chúng ta làm theo các bước:
Khởi tạo mảng kết quả ret, sắp xếp phrases.
Định nghĩa map m, n := kích thước phrases.
Với i từ 0 đến n-1: s = phrases[i], rspace = vị trí dấu cách cuối cùng. Thêm i vào m[s] (nếu không có dấu cách) hoặc m[s.substr(rspace+1)].
Với i từ 0 đến n-1: s = phrases[i], lspace = vị trí dấu cách đầu tiên. x = s (nếu không có dấu cách) hoặc s.substr(0, lspace).
Nếu m có khóa x: v = m[x]. Với mỗi j trong v, nếu v[j] != i, thêm phrases[v[j]] + s.substr(x.size()) vào ret.
Sắp xếp ret, loại bỏ trùng lặp, trả về ret.
Ví dụ (C++)
Hãy xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
vector <string> ret;
sort(phrases.begin(), phrases.end());
unordered_map <string, vector <int> > m;
int n = phrases.size();
for(int i = 0; i < n; i++){
string s = phrases[i];
auto rspace = s.rfind(' ');
m[rspace == string::npos ? s : s.substr(rspace + 1)].push_back(i);
}
for(int i = 0; i < n; i++){
string s = phrases[i];
auto lspace = s.find(' ');
string x = (lspace == string::npos? s : s.substr(0, lspace));
if(m.count(x)){
vector <int>& v = m[x];
for(int j = 0; j < v.size(); j++){
if(v[j] != i){
ret.push_back(phrases[v[j]] + s.substr(x.size()));
}
}
}
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
};
int main(){
vector<string> v = {"mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"};
Solution ob;
print_vector(ob.beforeAndAfterPuzzles(v));
}
Đầu vào
["mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"]
Đầu ra
[a chip off the old block party, a man on a mission impossible, a man on a mission statement, a quick bite to eat my words, chocolate bar of soap, ]