Giả sử chúng ta có một danh sách các cụm từ, hãy tạo một danh sách các câu đố Trước và Sau. Ở đây một cụm từ là một chuỗi chỉ bao gồm các chữ cái thường và khoảng trắng. Không có khoảng trống nào ở vị trí bắt đầu và kết thúc. Không có dấu cách liên tiếp trong một cụm từ.
Câu đố trước và sau là các cụm từ được tạo thành bằng cách ghép hai cụm từ trong đó từ cuối cùng của cụm từ đầu tiên giống với từ đầu tiên của cụm thứ hai. Chúng ta phải tìm các câu đố Trước và Sau có thể được tạo thành bởi mỗi hai cụm từ cụm từ [i] và cụm từ [j] where I! =J. Lưu ý rằng thứ tự khớp hai cụm từ rất quan trọng, chúng tôi muốn xem xét cả hai đơn đặt hàng.
Chúng ta sẽ tìm thấy một danh sách các chuỗi riêng biệt được sắp xếp theo từ điển. Vì vậy, nếu thông tin đầu vào giống như các cụm từ =["tuyên bố sứ mệnh", "ăn nhanh", "một con chip khỏi khối cũ", "thanh sô cô la", "nhiệm vụ bất khả thi", "một người đàn ông đang thực hiện nhiệm vụ", " đảng khối "," ăn lời tôi "," thanh xà phòng "], thì kết quả đầu ra sẽ là:[" một con chip khỏi đảng khối cũ "," một người đàn ông trong một nhiệm vụ bất khả thi "," một người đàn ông trong một tuyên bố về nhiệm vụ "," cắn nhanh để ăn lời tôi "," thanh xà phòng sô cô la "].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định mảng chuỗi ret, sắp xếp mảng cụm từ
-
xác định một bản đồ m, n:=kích thước của mảng cụm từ
-
cho tôi trong phạm vi từ 0 đến n - 1
-
s:=cụm từ [i], rspace:=chỉ mục của khoảng trắng từ phía bên phải
-
insert I vào danh sách được đặt tại m [khi rspace là null thì s, nếu không thì tìm chuỗi con của s lên đến rspace + 1]
-
-
cho tôi trong phạm vi từ 0 đến n - 1
-
s:=cụm từ [i] lspace:=chỉ mục của khoảng trắng từ phía bên trái
-
x:=khi lspace là null thì s, nếu không thì tìm chuỗi con của s từ 0 đến lspace]
-
nếu m có x là khóa
-
v:=m [x]
-
cho j trong phạm vi 0 đến kích thước của v
-
nếu v [j] không phải là tôi, thì
-
chèn các cụm từ [v [j]] + chuỗi con của s (tối đa là x) vào ret
-
-
-
-
-
sắp xếp lại
-
xóa duy nhất của ret và trả lại ret
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách 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;
}
};
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, ]