資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中的前後拼圖
假設我們有一列短語，生成一列前後拼圖。這裡一個短語是一個只包含小寫字母和空格的字串。開頭和結尾沒有空格。短語中沒有連續的空格。
前後拼圖是由兩個短語合併形成的短語，其中第一個短語的最後一個詞與第二個短語的第一個詞相同。我們必須找到可以透過每兩個短語phrases[i]和phrases[j] (其中i != j)形成的前後拼圖。注意，匹配兩個短語的順序很重要，我們要考慮兩種順序。
我們應該找到一個按字典序排序的唯一字串列表。所以如果輸入類似於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"], 那麼輸出將是：["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"]。
為了解決這個問題，我們將遵循以下步驟：
定義一個字串陣列ret，對phrases陣列進行排序
定義一個對映m，n := phrases陣列的大小
對於I從0到n-1
s := phrases[i]，rspace := 從右側的空格索引
將I插入到m[如果rspace為空，則為s，否則找到s直到rspace+1的子字串]位置的列表中。
對於I從0到n-1
s := phrases[i]，lspace := 從左側的空格索引
x := 如果lspace為空，則為s，否則找到s從0到lspace的子字串
如果m包含鍵x
v := m[x]
對於j從0到v的大小
如果v[j]不等於I，則
將phrases[v[j]] + s的子字串（直到x的大小）插入到ret中
對ret進行排序
刪除ret中的重複項並返回ret
示例 (C++)
讓我們看下面的實現來更好地理解：
#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));
}輸入
["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"]
輸出
[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, ]
105 次瀏覽
